Friday, March 28, 2008

Walking over a large list. Slowly and safely.

In my timer code I've deliberately avoided having to deal with the problem of the possibility of the concurrent list traversal - since it is basically an array of lists, and each list I walk exactly in one shot (under the assumption that I would not have the 200000 timers to shooting at the same time) - so the problem does not exist.

However, it is more of a corner case than the rule - I'll need to walk potentially large lists of stuff (not 200K, but 64K quite easily) - and send their contents very slowly and carefully (a blast of 64K of the packets even on the fastest link is a guarantee that you clog the pipe somewhere inbetween and lose the packets - so the list will need to be walked slowly.

There are a couple of interesting articles around the subject - iterators on pine wiki, and continuations.

Continuations are basically a way to reimplement the threads (which I do not want), so I will probably just use the iterator functions, which will take the saved state as one of the parameters - and lock the list items as I hold on to them - to prevent the annoying bugs which come when the two pointers point to the same location, and one piece of code suddenly decides to free it. I've had this kind of bug this weekend - almost a day of a lot of fun to track down, since it is hard to consistently reproduce, and caused more or less random areas of memory to get smashed - depending on what was the sequence of events. Luckily at least I knew the new code that started all of this - but the presence of a second bug of a similar kind did not make the things better :-) That one got smashed with the help of valgrind. Although I also long wanted a chance to play with ElectricFence - so this weekend I'll probably give it a shot - I think I did not yet exhaust my bugs-per-KLOC ratio for the past weekend's code spurt :-)

No comments: