7.27.2011

Offline repost #1: Doomed lists

It's interesting how often I consider certain features more valuable than sheer performance when designing stuff for ITK. For example, linked lists has always been a long story with me and the associated implementations. Especially the inline argument was one the reasons why I previously chose C++ but forgot about when having settled with C. However, I'm still working on perfection the concept and learned a completely different side of iterators that doesn't count on beeing generic but simply more memory-efficient! Yes, that's right. Imagine you have a singly linked list. How do you want to operate on it? An internal selector, so that only one selection is possible and pollutes memory for multiple, non-paralelly accessed lists? No, that's just too much of a waste. So the only really viable solution is to use a special selector providing the necessary selection data, which's atleast three pointers for a parent-bounded singly linked list. All in all it's an iterator. I saw that coming before, but so often I started doing something different. Back to the original topic, designing the parameters of iterators is also quite questionable. I mean did you ever thought about whether to use either two functions for insert/deleting before and after OR using just one and passing a parameter indicating the desired item? I must say I'm currently preferring the latter one cause it simplifies code and works the same for both directions if you carefully arrange all next/prev start/end relations in a two-entry array. Sure, you need to check some more paramaters, but it also gives you a lower code amount (remember, that's also for small devices with less memory) and reduces the amount of corrections you when something went wrong due to only half the code! It's definitely not as performant, but as so often in my later programming experiences, I see a direct connection between small, less fast but efficient and maintainable code and slightly different, generated code with more performance on systems with much memory. I can't help, but this is what my world's about: performance, memory, efficiency and improving the lower layers. All the hidden "secrets" non of my fellow students care about or want (or maybe can) understand. Some reallife company for such things would be lovely.

Oh and just for the notes: singly linked lists are extremely crappy if it comes to O(1) interfaces. I mean you can either provide a unified set for every kind of list (iterator) and insert a plethora of 1->n iterations without the users knowledge or simply only only provide O(1) functionality while imiting the interface. The latter one is my favourite but brings strange things having the ability to insert stuff at start and end, but only remove from the start cause you can't link back from end to it's previous element and so on. Really weird and crappy but faster than otherwise. I'll have to take a look what GCC puts out as assembler when inlining all modules into one single cpp. I could only guess that it's either capable of removing all the parameter checks (would require some flow dependency checks) or doesn't even remotely do something about it. But it's GCC after all, a massive pile of code made to support even the most trivial things when doing it by hand. So removing parameter checks IS a trivial things for certain cases, but maybe not in all that C supports. The more I think about it, the more I understand why it must be easier to write a C optimizer than a C++ optimizer. Or they're converting C++ to C, which I guess is the usual case.

No comments: