3 ms·

The article is still wrong - iterating through a linked list is O(N log(N) sqrt(N)). You can't have infinite nodes in a 16-bit, 32-bit, or even a 64-bit addres

The article is still wrong - iterating through a linked list is O(N log(N) sqrt(N)). You can't have infinite nodes in a 16-bit, 32-bit, or even a 64-bit address space - to deal truly with N, one must consider the more generic case of a variable address encoding, which has a variable size (log(N)) and associated lookup etc. costs as the number of nodes grows. This is the motivation behind e.g. the "x32 ABI" in Linux: All the power of x86-64 instructions, with none of the additional cache pressure/overhead of 64-bit pointers - log(32) being cheaper than log(64). ...ahh, being this explicit in your Big-O notation is probably not that useful, usually, although I've seen it occasionally in papers (where they're quite explicit about also counting the number of bits involved). Maybe they're dealing with BigNum s, which would make it a practical concern? The key takeaway is this: > That I use Big O to analyze time and not operations is important. Time depends on compiler settings, allocation strategy, and a whole host of other factors that are outside the purview of your algorithm. Operations is a lot easier to contrast and compare between different algorithms, the meat of what you're trying to do most of the time. Both are valid choices, just know which one you're dealing with. The time factors are good to be aware of, to be sure - the performance pitfalls of (potentially) highly fragmented, hard-to-prefetch linked lists over unfragmented flat arrays should be well known to anyone charged with optimizing code - but it's probably easier to think of them as some nebulous large time constant (as even array iteration is going to hit the same worse-than-O(N) behavior, although with proper prefetching the bottleneck may become memory bandwidth rather than memory latency) and deal with those differences with profiling and other measurements, instead of Big-O notation.

AstralStorm 10y ago
Sorry, but for asymptotic analysis pointer size is considered constant. So, even the smallest last uses B-bit pointers. Feel free to introduce a packed pointer type that would be asymptotically faster, but then it is a different data structure.
- MaulingMonkey 10y ago
  Since when does a linked list mandate unpacked, fixed-width pointers? Citation needed! I note they are not called pointered lists, and challenge the assumption that they even need use pointers - or do you think this abstract computer science concept is something different when applied to disk storage formats by using file offsets as the link? Linked lists as a concept date back to ~1955, when RAM was very expensive - magnetic-core memory being just introduced. Think punch cards. Returning back to the modern era - one also does not need a packed pointer type, merely support for multiple pointer sizes within the same process, and the ability to dynamically dispatch to the correct one for the job. And multiple pointer sizes within the same process are a matter of routine: In the 16-bit C era, vanilla "near" and "far" pointers very clearly weren't the same size. A very similar situation occurs under the hood when dealing with 32-bit processes on 64-bit windows via WoW64, which can lead to some interesting complications if you use a 64-bit application to create a crashdump for a "32-bit" process, where you can actually inspect the 64-bit side of things too (fire up WinDbg and dig in: https://msdn.microsoft.com/en-us/library/windows/desktop/aa384163(v=vs.85).aspx https://msdn.microsoft.com/en-us/library/windows/desktop/aa3... ) This is to say nothing of 20+ byte member function pointers on 32-bit architectures because C++ is only out-crazied by C++ compilers. Or dealing with the complications of multiple pointer sizes via shared memory. Or dealing with file "pointers" (read: offsets) of varying sizes.

AstralStorm 10y ago

Sorry, but for asymptotic analysis pointer size is considered constant. So, even the smallest last uses B-bit pointers. Feel free to introduce a packed pointer type that would be asymptotically faster, but then it is a different data structure.

MaulingMonkey 10y ago
Since when does a linked list mandate unpacked, fixed-width pointers? Citation needed! I note they are not called pointered lists, and challenge the assumption that they even need use pointers - or do you think this abstract computer science concept is something different when applied to disk storage formats by using file offsets as the link? Linked lists as a concept date back to ~1955, when RAM was very expensive - magnetic-core memory being just introduced. Think punch cards. Returning back to the modern era - one also does not need a packed pointer type, merely support for multiple pointer sizes within the same process, and the ability to dynamically dispatch to the correct one for the job. And multiple pointer sizes within the same process are a matter of routine: In the 16-bit C era, vanilla "near" and "far" pointers very clearly weren't the same size. A very similar situation occurs under the hood when dealing with 32-bit processes on 64-bit windows via WoW64, which can lead to some interesting complications if you use a 64-bit application to create a crashdump for a "32-bit" process, where you can actually inspect the 64-bit side of things too (fire up WinDbg and dig in: https://msdn.microsoft.com/en-us/library/windows/desktop/aa384163(v=vs.85).aspx https://msdn.microsoft.com/en-us/library/windows/desktop/aa3... ) This is to say nothing of 20+ byte member function pointers on 32-bit architectures because C++ is only out-crazied by C++ compilers. Or dealing with the complications of multiple pointer sizes via shared memory. Or dealing with file "pointers" (read: offsets) of varying sizes.