In short, it’s important to understand the problem before trying to solve it.
Well, that’s half of it. The other half is knowing that there’s a single x86 instruction that can replace a chunk of your code and give you part of the answer in the blink of a CPU’s eye :)
I would argue that the instruction probably takes a relatively long time from the perspective of the CPU, but yea the it’s also important to understand your tools!
And understand if there is a problem. If you haven’t profiled then optimisations are probably a waste of time.
One of the major things I do is write high-speed network traffic capture engines, with TCP stream reassembly and protocol decoding and all that jazz.
Obviously we want to dump state from the TCP reassembly engine when we haven’t seen anything on that stream for a while (or so little that it’s a slow loris type attack, whatever).
In the beginning we had a beautiful complex heap thing with connection records ordered by next time check thing and each time we saw traffic we’d move the records around, do timeouts, etc.
Turns out just having a doubly-linked list of connection records works a lot better. Each time we see a packet for a connection we look the connection up via a hash on the five-tuple; the record has several chase pointers that link it into various lists.
One of the lists is the timeout list. Every time we get a packet for a connection, we move it to the back of the list, an O(1) operation, and update the seen time for that record. Every so often, we walk from the start of the timeout list until we see a time that is new enough that it hasn’t timed out, and we stop. This is O(n) in the number of simultaneous connections.
Sure it’s not as fancy or cool as a heap (which has better bounds for every operation involved except timestamp update), but it’s a whole lot simpler and scales well enough that it’s been overall faster for up to a couple of hundred thousand simultaneous connections.
But When somebody asks me ‘what programming language is fast ?’.
I usually reply, those are the ones that can saturate a modern network pipe, with useful data, after transforming it, coming in on another pipe.
I do not know what language you use, but I suspect, given your type of work, it is one of the ‘fast ones’.
That part’s in C. :)
This is a bit off-topic but do you have any recommendations for books that are similar to Network Algorithmics in content?
I’m afraid I’m not familiar with that one (though I just bought a copy off Amazon, so thank you for the recommendation).
Most of what I’ve read for this sort of thing are protocol specifications (RFCs, etc) and other (open source) implementations. I’m sorry that I couldn’t be more helpful.
I am impressed, but there’s a part of me that would rather see the asymptotically better solution. Here are the tradeoffs from my point of view.