[DP-03] Improve efficiency of message matching

[edsko]

[Imported from JIRA. Reported by Edsko de Vries @edsko) as DP-3 on 2012-10-15 09:20:36]

In particular, storing messages by type could be very beneficial.

[hyperthunk]

So would we store the accepted mailbox as Map Fingerprint (StrictList a) or some such? Is Map the right data structure for this or donee want a strict version?

[edsko]

You have to be very careful here: you still need to guarantee ordering. If a process does a receiveWait for type A or type B then we need to make sure that if a message of either type exists they are delivered in the order that they were received.

[hyperthunk]

You have to be very careful here: you still need to guarantee ordering.

Yes of course, I was jumping ahead without thinking there. I suspect then, some kind of custom data structure that maintains the priority property but supports searching/inserting by key. Ralf Hinze et al present a Priority Search Queue which IIRC was used (or adapted) in the GHC IO manager, so perhaps we can take some inspiration from there. The primary difference is that we want to select by a range of keys and then order by priority.