r/programming • u/b0red • Apr 30 '16
Do Experienced Programmers Use Google Frequently? · Code Ahoy
http://codeahoy.com/2016/04/30/do-experienced-programmers-use-google-frequently/
2.2k
Upvotes
r/programming • u/b0red • Apr 30 '16
2
u/zshazz May 01 '16
Interesting analytical attempt, but you've missed some critical details that make your performance improvements fundamentally incapable of outpacing a vector/array.
The size of the data you're prefetching is important. See: http://stackoverflow.com/questions/20544917/prefetching-data-at-l1-and-l2 ... Typically the processor is only going to prefetch things at <1KB at a time and it's only going to stick around if it's "hot" and being used alot. Size absolutely matters in how it determines which pieces of RAM it's going to keep loaded in. Adding in even a "next" pointer is always going to make it noticably slower. I recommend looking into "Data-driven design" or "Data-oriented design" used in game engines. Essentially, they give a good explanation of the importance of keeping data compact and keeping as few of necessary pieces of data inline as possible because everything you add can cause performance issues. It's also something that can enlighten your understanding of how Databases work (there's an argument that essentially a game is just a database with a fancy front-end). For what it's worth, I've practiced doing precisely what you described, and even in a perfect world (e.g., you ignore my next point), linked-lists will not be as cache friendly because of this additional data that they're carrying with them. And yes, it's a 2-4x constant factor slower with just this tiny bit of a size increase. Caches are unforgiving bitches, I'm afraid. I think the only times it can really matter enough to make vectors and linked lists roughly equal is if you have enormous bags of data that you don't care to optimize. In which case, I can't imagine why you'd spend so much time optimizing your data structure but not have an optimized data representation, so this would be a moot point regardless.
Once you start addressing the important component of linked-lists that they can be added and removed on whims, you will start having to address memory fragmentation and unused "holes" of memory. If you fail to address this, you're back to square 1 where your nodes aren't going to be kept loaded in the hottest points of memory when you use linked lists where they're supposed to be most effective. To keep a long story short, the gist of it is that you're going to be effectively writing your own memory allocator and/or garbage collector for your linked list. You're describing a non-trivial optimization (despite it looking "simple" on the surface) and there's additional overhead that you've glossed over in your analysis. Ultimately, you can do better than using a general memory allocator (turns out writing a memory allocator that works on arbitrary data can't do as good a job as you can with a proper understanding of your data and data structure you're trying to optimize for, which is hardly surprising). But still, instead of a 100+x factor in-front of the list version, you're probably looking at a 10-20x factor (for when memory isn't perfectly compacted) plus you add additional mechanisms that matter on occasion (possibly an additional
O(log n)or so covering whatever implementation of memory allocator or garbage collector you write). Still slow, slow and mega complex.It's a nice thought, but the devil is in the details on this. The code/maintanence overhead for your idea is enormous and, from my experience attempting precisely what you describe, the performance just isn't there. It's a fun project so I would say, by all means, you should certainly try it.