Convert Gathers To Scatters

Summary

It is more efficient to give a data producer information about its consumers, than to allow multiple consumers to redundantly access the same producer multiple times. Converts N reads/N writes into 1 read/N writes.

Outline

Assume you have a relationship between consumers and producers,

 +----------+  1      n +----------+
 | Consumer |<>-------->| Producer |
 +----------+           +----------+

where you have N consumers and M producers, where N > M. An example could be a mesh, where the consumers are vertices written to a display list and the producers are the results of vertex calculations. In a mesh, one vertex would be used many times in the display list, hence a naive solution would be:

FOREACH point to be drawn READ vertex data WRITE vertex data to display list ENDFOR

This would be using the relationship "consumer gathers from producer". Notice that the number of reads and writes are 2N.

Instead, if one considers the inverse relationship "producers scatter to consumers", then since each producer can have more than one consumer, we let each producer have a list of consumers. Hence, in our example:

FOREACH vertex READ vertex data FOREACH position in display list WRITE vertex data to display list ENDFOR ENDFOR

For this algorithm, the number of reads and writes is M + N which is less than 2N because M < N. -- PalKristianEngstad.

When to use

More generally this pattern is applicable where each consumer polls n producers and each producer supplies m consumers (rather than just for m=1 as described above). Use the pattern in reverse when m > n :-) I've used it with a substantial saving even when m=n. Here the saving arose because a significant fraction of times the supplier had nothing to supply. The overhead for determining whether there was anything to supply was cut by a factor of m. -- JamesCrook

Notes

Someone mentioned ObserverPattern as an "implementation hint". ObserverPattern is related to this, but where Observer uses a "pull" subscription mechanism, this uses a "push" mechanism. This is a good case where optimization and re-use might be at odds - a pull mechanism is easy to extend by adding observers. A push mechanism is faster in most cases but adding observers is more difficult. Also, a pull mechanism is easier to implement since each Observer can know in advance which objects it will be observing - so the implementation can simply reserve an object variable for a pointer to the observed object. With a push mechanism, every observer must be known - either in advance [which hinders re-use] or else via some form of list. With these caveats, there is no reason an implementation using ConvertGathersToScatters could not be dynamically updated with new observers, and indeed it will still perform faster than the ObserverPattern in the case of infrequent updates.

This contrast can also be viewed in system architecture - an interrupt-driven I/O system uses a "push" architecture, while a polling I/O system uses a "pull" architecture. Interrupt-driven systems are well-known to achieve higher performance, and where events are sparse a polling architecture can waste considerable time discovering that there is nothing to do.

Another example is in internet radio. Since IP does not support broadcast or multicast messaging across the whole internet, any internet "broadcast" must in fact be sent to each consumer separately. Thus, an internet radio "station" has bandwidth requirements which scale as its number of listeners scales. This is ObserverPattern par excellence. Instead, the station should register new listeners and send multicasts to them all over a protocol which supports it [e.g. IPv6]. Their bandwidth requirements are now very small. Note that no functionality is lost - but the transmitter is more complex.

Also see the ConsumerProducer DesignPattern.