[HN Gopher] The true cost of linked lists
___________________________________________________________________
The true cost of linked lists
Author : karroum
Score : 220 points
Date : 2022-06-06 10:16 UTC (12 hours ago)
(HTM) web link (ykarroum.com)
(TXT) w3m dump (ykarroum.com)
| cycomanic wrote:
| As a side note I really wish people would stop putting the result
| tables instead of otting the results. The mental complexity of
| processing the results in table format is orders of magnitude
| higher, while one needs to go through every line and parse the
| number one to understand the main point it could be seen with a
| single glance if it was a plot. This gets even worse on mobile
| which wraps the output lines, like its the case here.
| omginternets wrote:
| When are linked lists actually _good_? Everything I read about
| them suggests they have rotten performance, yet I see them
| employed in various places all the time, by competent engineers
| who are definitely aware of their limitations.
|
| One case that seems to make sense is any time you want to do
| constant-time pops/appends... maybe?
| superdimwit wrote:
| One nice property is their stable addressing. A linked list
| element won't move once allocated.
| chii wrote:
| > A linked list element won't move once allocated.
|
| only pertains to languages like C. In a virtual machine
| language like java, this isn't a property that can exist
| (there's no such thing as an address - at least as far as the
| language is concerned).
| ziml77 wrote:
| A reference in Java can essentially be thought of as a
| pointer into a virtual address space. The JVM can move
| around the location of an object in the system's actual
| memory, but as far as anything holding reference is
| concerned nothing has changed.
| recursive wrote:
| And a reference to an object that's in an array won't be
| invalidated if that object is moving around the array or
| even removed entirely. It's still a C concern.
| di4na wrote:
| Anytime you do something that is immutable with probable change
| somewhere inside that is not easy to handle with far mor
| complex datastructure. In particular linked list are great for
| heterogeneous cells type.
|
| Vectors and arrays have the problem of needing contiguous
| memory. If an inner cell can have different size, or worse
| change it mid work, things get ugly really fast.
| MontyCarloHall wrote:
| Why not just implement this as an array of constant width
| pointers to the heterogeneous data types?
| LorenPechtel wrote:
| Which is what happens in most modern languages. The items
| in your list are objects--which internally are just
| pointers to the data. There's no performance penalty for
| having variable-sized objects in the list.
| leeter wrote:
| Operating systems where you need to be able to atomically
| insert or remove from a list. Because the links are just
| pointers and the memory can be managed after the swap you can
| use atomics to compare and swap pointers. This allows for the
| RCW mechanisms the linux and NT kernels depend on to work.
|
| This also technically applies to lockless data structures for
| some high performance code too. But those tend to be much much
| more tightly tuned for performance and the specific CPU they
| are intended to run on.
| [deleted]
| shultays wrote:
| They are sometimes used as intrusive lists but a generic one
| rarely used.
|
| Inserting an element in middle is probably only legit use but
| it is kinda rare to have large enough data that you frequently
| insert in mid
| [deleted]
| Ono-Sendai wrote:
| Linked lists are great for free lists in memory allocators.
| SAI_Peregrinus wrote:
| Writing a system allocator (malloc).
|
| They're also more useful on microcontrollers where there's no
| cache, no prefetcher, etc. Less code needed for the data
| structure means more free space for business logic, and there's
| no performance penalty for bad cache locality on a system
| without any cache. Also a hash table has to hash each input,
| which is a significant amount of work for many
| microcontrollers.
| marginalia_nu wrote:
| I think the problem is that we're thinking about linked lists
| like they are taught in intro to algorithms. Like
| ListNode* a = new ListNode('A'); ListNode* b = new
| ListNode('B'); ListNode* c = new ListNode('C');
| a.next = b; b.next = c;
|
| That's a dumb way of implementing a linked list with no
| redeeming features outside of explaining the concept.
|
| This is a linked list with the same shape as the list above,
| but with completely different performance characteristics:
| int* data = new int[3]; data[0] = 'A'; data[1] =
| 'B'; data[2] = 'C'; int* links = new int[3];
| links[0] = 1; links[1] = 2; links[2] = -1;
|
| With some elaboration (say exchange the arrays for a mmap-call,
| turn it into a tree instead of a list) and you're basically
| looking at the guts of a DMBS or a file system.
| BosStartup wrote:
| This has the same issues as just using an array to store the
| data. If you remove a node in the list now you have to
| rewrite all the values in the links array. If you don't do
| that then you have to implement your own garbage collector
| and pay the penalty periodically.
| marginalia_nu wrote:
| > If you remove a node in the list now you have to rewrite
| all the values in the links array.
|
| You actually don't. You can just keep two lists within the
| same structure, one for occupied nodes and one for free
| nodes, and just move deletions to the head of the free
| nodes list.
|
| Example List: Data: [ a, 0, c, d, e ]
| Links: [ 2, -1, 3, 4, -1 ] Head of occupied
| nodes: 0 Head of free nodes: 1
|
| Link shape: Occupied Nodes: 0 -> 2 -> 3 ->
| 4 -> [] Free Nodes: 1 -> []
|
| To Delete C: data[2] = empty // free data
| links[2] = 1 // Repoint 2 -> 1 links[0] = 3 //
| Repoint 0 -> 3 firstFreeNode = 1
|
| This changes the data such: Data: [ a, 0,
| 0, d, e ] Links: [ 3, 2, -1, 4, -1 ] Head
| of occupied nodes: 0 Head of free nodes: 2
|
| New shape: Occupied Nodes: 0 -> 3 -> 4 ->
| [] Free Nodes: 2 -> 1 -> []
| MontyCarloHall wrote:
| >turn it into a tree instead of a list
|
| Sounds a lot like "draw the rest of the damn owl." [0] :-)
|
| DBMSs and file systems use (extremely sophisticated) tree
| structures under the hood. Not sure that "linked lists are
| useful if the linking topology is much more complicated than
| a simple line" is a ringing endorsement of them.
|
| [0] https://pbs.twimg.com/media/Bs13i6LCcAAvwCf.jpg
| marginalia_nu wrote:
| My point is that this general sketch of a layout with
| arrays of offset pointers roughly generalizes to something
| like a B or B+-tree fairly well, and that's a fairly simple
| data structure. You can absolutely implement a file system
| with passable performance with either of those tree
| structures.
|
| ( Here's an enjoyably lucid explanation on how to draw such
| an owl: https://www.youtube.com/watch?v=aZjYr87r1b8 )
| ziml77 wrote:
| Is there a reason the keep the data and the indices in
| different arrays? Unless you're navigating to an item by its
| position in the linked list, you're going to be checking the
| data at each node and then reading the next index to traverse
| forward. Since you're reading both, wouldn't it be better to
| make the index of the next node intrusive?
| marginalia_nu wrote:
| The design is mostly to provide a clear enough example, you
| can of course interlace them.
|
| It depends on the use case.
|
| If you're doing a lot of navigating over links before you
| reach the destination, maybe you want them separate. Could
| also be the data is large, even maybe stored on disk while
| the links are in memory, or whatever. There's a thousand
| different scenarios with different optimal arrangements.
| magicalhippo wrote:
| It allows you to reorder the data, say sorting it, without
| moving the actual data. If the element type is say a
| struct, this can be a huge performance win.
|
| It also allows you to keep multiple different lists to the
| same data, say sorted by different fields in the struct.
| dudul wrote:
| I believe they can also be useful to share data between
| instances in the case of immutable structure. Prepending to an
| immutable linked list is quasi-free in terms of memory usage.
| deathanatos wrote:
| > _When are linked lists actually good?_
|
| When the use case requires insertion/removal from the middle of
| the list. An LRU cache is about the most common use case I've
| run across. (The "LRU" part requires it to often bump an item
| to the end of the list, so LL's excel here, as we can shift the
| element's position in the list in O(1) time. An LRU structure
| would normally pair the LL with a HashMap, which maps the
| cached item to its LL entry, so that we've also got a O(1)
| search into the LL, and don't hit the problem in the article.)
|
| > _yet I see them employed in various places all the time, by
| competent engineers who are definitely aware of their
| limitations._
|
| I see them employed very, very rarely. Vectors1 are by far more
| common in every codebase I've ever worked on. (And should be
| one's default, IMO, if all you need is a container of stuff
| that you're going to iterate over, which is the usual case, for
| the reasons in the article.)
|
| 1ignoring cases where a hash(map|set) is required; then our
| codebase uses that, b/c that's what's needed.
| verall wrote:
| This is exactly correct, since at least in C++, adding
| elements to any other data structure can invalidate the
| stored iterators/references in your hashmap. std::list will
| mean you pay a slight cost when adding new entries, which if
| your cache is working is hopefully not so often, or the
| malloc is already dominated by whatever is being cached.
| gpderetta wrote:
| In c++, std::deque is better than std::list as an address
| preserving backing store as it requires less memory
| allocations, less space overhead and objects will be closer
| together.
| deathanatos wrote:
| > _std::deque is better than std::list as an address
| preserving backing store_
|
| std::deque will invalidate iterators in some cases. Since
| my example above was an LRU cache, the cache's removal of
| an item from the middle of the list (to shift it to the
| end) is one of those actions that would invalidate
| iterators in a std::deque.
|
| (Not to malign std::deque: it is a useful datastructure
| in its own right, and if you need queue-like semantics
| (e.g. cheap remove from front), it's a better choice than
| a LL, and both are better than vectors for that purpose.
| I find deque's internals to be a bit weird ... my goto
| would normally be a ringbuffer, but the STL provides
| deque instead, so eh, it's good enough, if a bit odd
| IMO.)
|
| (Cf. https://en.cppreference.com/w/cpp/container/deque)
| MontyCarloHall wrote:
| >One case that seems to make sense is any time you want to do
| constant-time pops/appends... maybe?
|
| Yes, and constant time insertions/deletions in the middle of
| the list, assuming you know the address ahead of time.
|
| This makes them great as backing queues in an LRU cache: given
| some key/value pairs, have a linked list whose nodes map to
| each key. Additions to the K/V store gets appended to the LL.
| This lets you easily remove the oldest n elements in the K/V
| store, by traversing from the head of the LL. It also lets you
| efficiently remove arbitrary elements from the K/V store, if
| you store the addresses of each LL node as values in the K/V,
| since deletions in the middle of the LL are constant time.
|
| >yet I see them employed in various places all the time
|
| I agree, however, that most LL applications (like the one I
| just mentioned) are fairly niche. LLs are overused because
| they're dead simple to implement and commonly taught in intro
| CS classes.
| alex_smart wrote:
| I have seen highly successful proprietary trading firms
| implement their order books using linked lists (more like a
| linked list for each level of the order book, with the levels
| themselves arranged in a linked list). Obviously they use a
| custom allocator or an object pool to make sure that the cache
| performance isn't completely atrocious.
| jerf wrote:
| "When are linked lists actually _good_? "
|
| Your question is more accurate than you realize! Because the
| answer is... _the past_.
|
| Up until about the 486/50MHz era, CPUs and memory were attached
| to each other; one CPU cycle was approximately equal to one
| memory access. I don't mean that you could reach out to RAM in
| exactly one cycle and get a value, there were still some CPU
| caches and other considerations, but it was much _closer_ to
| that ideal than on modern systems. And if you go back in time
| even farther, that actually was the case (Commodore 64, for
| instance).
|
| (I don't know if there was ever a "true" 486/66 system, but I
| remember that as the CPU/clock speed where the CPU finally and
| definitively detached from RAM speed because that was generally
| a double-clocked 486/33 from the RAM's perspective. I can't
| quite remember the marketing term that was used. It's a dead
| term now because everything works that way.)
|
| In those circumstances, traversing a linked list was not
| necessarily _that_ much more expensive than a vector, and you
| could win on the other things a linked list can do faster than
| a vector, like insert in the middle, especially an insert in
| the middle when you were traversing the list anyhow. You could
| also win on a linked list containing a relatively large value
| organized just by pointers; a sort on the linked list
| manipulating just the pointers could win versus a sort that was
| trying to move around larger values constantly during the sort.
| And so on.
|
| When memory accesses aren't hundreds and hundreds of CPU
| cycles, when your hardware doesn't have prefecting implemented,
| when your pointers aren't 64bits wide, when you aren't on
| modern systems essentially designed to make vector-based access
| go zoom, linked lists make a lot more sense.
|
| This is how they got embedded in curricula so hard that they
| are taught to this day. They used to be a very important data
| structure. Now they're an antipattern. It happened gradually,
| though, and it doesn't help that linked lists are just about
| the easiest non-trivial data structure to teach and I'm not
| sure they could get removed from the standard curriculum for
| that reason alone.
|
| "One case that seems to make sense is any time you want to do
| constant-time pops/appends... maybe?"
|
| Another problem linked lists have is that if you _know_ that 's
| what you're going to do, you can build vector-based solutions
| to that problem that work just fine. Vector-based stacks, for
| instance, are trivial, and O(1)-amortized for push and pop,
| which is good enough in practice. (A bit more care is needed
| than an only-growing vector but IIRC it can be done.) You need
| not just something linked lists are better at, but some bizarre
| cocktail of all the things they're just barely better at, and
| you still need to construct a win out of the combo. It's nearly
| impossible. Not quite impossible. I assume without looking that
| the Linux kernel still has some linked lists for good reason,
| as I'm sure if they could win on performance by removing them
| they would. But very hard.
| LorenPechtel wrote:
| I would think a queue would be best served by a linked list.
|
| Every pop moves the whole list unless you get fancy an
| implement it as an array with head and tail pointers and grow
| logic.
|
| If you keep a tail pointer inserts are likewise O(1).
|
| You rarely traverse them.
| jerf wrote:
| By data structure standards, the requisite amount of
| "fanciness" to implement a queue in a vector is table
| stakes, hardly even worth 10 minutes of class time at the
| sophomore level, if not simply given out as homework. It is
| no problem at all to put a queue in a vector. You'd need a
| doubly-linked list for this, too, and as the article
| mentions, your linked-list queue is likely to lose just on
| malloc & free (or local equivalents) versus the vector.
|
| (The best optimization you could do in such a case would be
| to allocate multiple slots per pointer, to amortize the
| malloc/free time. Then you'd want to run benchmarks to tell
| what the optimal amount of slots would be. If a vector is
| optimal, as I strongly expect it would be, the answer would
| come out to be, "all of them".)
|
| Modern processors move chunks of RAM around _really
| quickly_. They 're really optimized for it. It is one of
| the major things I'm referring to when I say our systems
| have been optimized for C. I often wonder about what an
| architecture designed in a world where linked lists were
| dominant would look like. However, it is certainly not this
| world.
| tobiasSoftware wrote:
| Circular buffers (your fancy implementation) are far
| superior for queues. Pretty much any modern vector like
| data structure is already going to have grow logic so
| adding head and tail pointers isn't too hard. However, as
| this article mentions, keeping memory compact is pretty
| important to speed, and circular buffers are able to do
| that while linked lists aren't.
| kevin_thibedeau wrote:
| The majority of microprocessors today are <200MHz, single
| core, single issue, with no cache. The world doesn't run on
| x64 and GPUs.
| Thomashuet wrote:
| The claim is that vectors perform better than lists even in a
| case where the theoretical complexity is in favor of the list:
| insertion in the middle. However the complexity of insertion in
| the middle is O(n) for both vectors and lists so the
| demonstration falls apart. A scenario where the complexity is
| different would be to copy and modify the first element: O(1) for
| lists and O(n) for vectors.
| gpderetta wrote:
| Insertion in a linked list is not O(n) though.
| [deleted]
| Sebb767 wrote:
| This is a common misunderstanding of computational complexity: It
| does not measure runtime, but how runtime changes depending on
| the input. Take the following two algorithms to find the square
| root of an int: result=None for i in
| 0...INT_MAX if i*i==searched result=i
| return i
|
| and for i in 0...searched if
| i*i==searched return i
|
| The first algorithm is O(1), the second is O(sqrt(searched)).
| Despite this, the second will clearly be faster in actual
| execution time. However, if your number range changes from 0-100
| to 100,000,000-250,000,000 , the former will still take the same
| time while the latter will take a lot longer. Now, in this
| example, this is quite obvious, but in the real world, you might
| encounter cases where a quadratic complexity solution is
| completely fine, until you have a lot of data and then suddenly
| your code slows to a crawl [0]. That's why we need computational
| complexity - it was never designed to perfectly measure or
| predict execution speed. This is also the reason constants are
| dropped in the notation.
|
| For real world performance, benchmarking is the key. Computers
| are very complex beasts and there are a lot of potential speedups
| or slowdowns you might never think of - memory bank order,
| thermal throttling and compiler optimizability can drastically
| change the results, just to name a few. Computational complexity
| is totally fine as an angle to find new possible optimizations,
| but in the end, you need to compare it to the other approaches
| and see what actually works.
|
| [0] https://news.ycombinator.com/item?id=21743424
| pjungwir wrote:
| It looks like you intended your first snippet to end with
| `return result` not `return i`, right?
|
| Mixing real-machine finitude with big-O theory often gives
| unexpected or unhelpful results. Once in an interview I argued
| that since hash tables have a finite number of buckets, at
| large enough scale they really have O(n) worse-case
| performance. That didn't go over very well. :-)
| ralusek wrote:
| I would have a huge problem describing the first one as O(1).
| Technically the complexity is min(searched, INT_MAX), but the
| algorithm would also fail to produce a result if it reaches
| INT_MAX.
|
| Functionally, though, I would describe this algorithm as O(N).
| It's just a straight up linear scan of the problem space. It's
| unbounded, with a worst case of O(Infinity) and no upper limit
| on what searched can be, but it's functionally O(N) regardless.
|
| O(1) needs to basically be something like a hash key/pointer to
| memory address to get the result you're looking for. It will
| not increase linearly as the problem space increases, whereas
| your first example increases exactly linearly.
| devmop wrote:
| It takes the same (huge) amount of time for all inputs -
| there's no early exit it always scans to INT_MAX. Hence O(1)
| glitchc wrote:
| This is incorrect. Putting a finite bound on n does not
| reduce n to 1. n is always meant to be a finite arbitrarily
| large value. n=INT_MAX qualifies as arbitrarily large,
| especially on a 64-bit system.
| 8note wrote:
| Consider n=INT_MAX*2 or INT_MAX^2 though.
|
| The behaviour does flatline as n approaches infinity
| Sohcahtoa82 wrote:
| Big-O notation says nothing about the overall absolute
| size. All that matters is how the amount of work scales
| with the input value.
|
| If an algorithm will _always_ take 1 billion years to
| complete regardless of the input, then it 's still O(1).
| PhineasRex wrote:
| There is no bound on n, it always searches to INT_MAX
| regardless of n.
| carnitine wrote:
| O(x) = O(1) if x is some finite constant.
| carnitine wrote:
| That's just not how complexity analysis works, if there's a
| bound anywhere, it is O(1). The behaviour below that bound
| may be of more practical importance, but it's not how
| O-notation works. The parent comment doesn't make a great
| deal of sense for other reasons, but your objections don't
| hold either.
| simiones wrote:
| By this logic, all programs that we run are O(1), since any
| data structure is in practice bounded in size by your
| available address space (+ disk space if we want to be
| pedantic). So, you can replace any loop over the elements
| of a DS with a loop over all memory in the address space,
| and you will get an O(1) algorithm.
|
| In the end, it's just not a useful way of modelling the
| problem.
| carnitine wrote:
| Yes, so ordinarily we analyse an idealised algorithm
| running on idealised machine. However if an upper bound
| is clearly introduced to this idealised setting, as in
| the root comment, then it can't be ignored.
| waynesonfire wrote:
| So an idealised machine doesn't have an arbitrary INT_MAX
| limit. The algorithms are O(n).
| l33t2328 wrote:
| But playing tricks with the INT_MAX limit ignores(or,
| more accurately, spits in the face of) the fact that we
| want our computers to pretend to be idealized machines.
|
| Floats aren't real numbers but we treat them like the
| mathematical object that they model for most purposes.
|
| Of course, being aware of the limits of our models are
| important, but abusing the tragic finitness of our models
| to "well actually" someone is generally not helpful.
| l33t2328 wrote:
| "The heat death of the universe will occur in finite time,
| therefore all algorithms you can ever use are O(1)" isn't a
| very helpful metric.
| mining wrote:
| I would probably argue that either the first algorithm is
| incorrect (because searched can be larger than INT_MAX) or the
| complexity of the second algorithm is bound both by O(searched)
| (or sqrt(searched), if implemented with more vigour) and O(1)
| (because the value of 'searched' is bound by a constant).
| Sebb767 wrote:
| I explicitly wrote
|
| > to find the square root of an int:
|
| so the value can't exceed INT_MAX :)
|
| Overall, I know the two algorithms aren't perfect, but
| they're a simple minimal example to show the difference
| between complexity and runtime.
| finalfire wrote:
| Question: is the first algorithm O(1) cause we treat INT_MAX as
| a constant, right?
| 1270018080 wrote:
| Correct.
| ChrisLomont wrote:
| You cannot talk about complexity without letting n-> infinity.
| Both algorithms are O(1), since n is bounded.
| Sebb767 wrote:
| True, but I wanted to go with a simple example to show my
| point.
| waynesonfire wrote:
| how is n bounded in the 2nd algorithm?
| xigoi wrote:
| If you assume that it's unbounded, then either the
| algorithms aren't solving the same problem or the first one
| is wrong, so it doesn't make sense to compare them.
| amag wrote:
| > For real world performance, benchmarking is the key.
|
| Only it's not enough. When you benchmark an O(N^2) algo may
| seem fine but then three years later the data has changed and
| is now an order of magnitude larger. So you need not only know
| your data, you also need to spend time thinking about how large
| it can become.
| robby_w_g wrote:
| > When you benchmark an O(N^2) algo may seem fine but then
| three years later the data has changed and is now an order of
| magnitude larger
|
| The GTA Online loading screen bug is a recent example of this
| problem, with its in-game purchasable items growing larger
| over time: https://nee.lv/2021/02/28/How-I-cut-GTA-Online-
| loading-times...
| [deleted]
| Ozzie_osman wrote:
| That's the point of O-notation though. It helps you know how
| your computation will degrade as your data grows.
|
| So you start with benchmarking your current data. You still
| need to always think about how your data will grow.
| quietbritishjim wrote:
| You seem to be agreeing with the parent comment's point. For
| example, there's this bit of their comment, which is almost
| verbatim what you replied back with:
|
| > ... you might encounter cases where a quadratic complexity
| solution is completely fine, until you have a lot of data and
| then suddenly your code slows to a crawl [0]. That's why we
| need computational complexity ...
|
| It seems like you're disagreeing only because you pulled out
| the one quote about benchmarking. But they were just saying
| that you need benchmarking to bootstrap the meaning of O(...)
| of an algorithm. That's the point that the original article
| missed, which is presumably why they described it as key.
| inetknght wrote:
| > _Only it 's not enough._
|
| True. But I do highly recommend watching Ben Deane's 2015
| talk about testing Battle.net. In it he briefly touches upon
| benchmarks and estimating algorithmic complexity. It's
| somewhat difficult to suss-out the details of it. But the
| short version is basically to run the benchmark with a few
| different sizes and then estimate the complexity growth from
| that.
|
| https://youtu.be/OPoZWnYIcP4?t=1035
| pphysch wrote:
| Question for PL implementation folks:
|
| How practical is it to implement a keyword/type that (portably)
| represents the L1/L2/LN cache size? Suppose I am implementing an
| algorithm or data structure and I really don't care what the
| $BLOCK_SIZE is, as long as it fits reasonably nicely in one of
| the lower caches as a sane default. It would be nice if I could
| do this with a magic keyword rather than hardcoding a default
| (1KiB) and forcing the end user to tune runtime params according
| to their hardware. Bonus if this can be used for static/stack
| allocations too.
| kllrnohj wrote:
| The `cpuid` instruction would tell you things like cache line
| size (and can enumerate cache topology). But you're then paying
| a cost for the value not being known at compile time, so you'd
| need to weigh the tradeoffs that may result from that.
| 0xffff2 wrote:
| For compiled languages, you would only every be able to do this
| for code compiled specifically for the target machine. I wonder
| if there are numbers out there for what percentage of code that
| applies to in the real world? My naive assumption is that it's
| a single digit percentage.
| zelphirkalt wrote:
| Finding the last element in a vector is initially given as
| theoretical complecity O(n) -- What? In any language I used, a
| vector would have information about how long it is and that would
| be used to get an index (length - 1) and the access is constant
| O(1).
|
| Not sure what kind of vectors are assumed in the article.
| dreamcompiler wrote:
| I had the same reaction. The only O(n) case I can think of is
| C's zero-delimited strings. But does anybody even still use
| these things nowadays?
| TingPing wrote:
| Millions of C projects, yes.
| bhuber wrote:
| On any sort of list structure, a "find" operation generally
| means searching the list in order for an element that satisfies
| a predicate, usually equality to a given value. The article
| could be more clear about this, but in this context finding the
| last element in a list means calling find() on a list where
| only the last element of the list matches the predicate. This
| is almost the worst case scenario (the worst case being no
| elements in the list match). If you read the code in the
| article, you can see it's using
| https://www.cplusplus.com/reference/algorithm/find/ to find an
| element in the list of value 1, after inserting that as the
| last element in the list.
|
| The point is, it doesn't matter if you know the length of the
| list, you still have to examine all the elements.
| nraynaud wrote:
| Geometry/topology is very often presented as soup of pointers,
| (think of doubly connected edge list, Quad-edge, etc.) I have
| personnally always implemented these with pointers, because it's
| at the tip of my skills and that's how they are presented on the
| internet ; but I'm curious to know if people more confortable
| with topologies and meshes use a different memory representation.
| ordu wrote:
| I think, that they presented on Internet as a soup of pointers,
| because it is the obvious and general way to do it. Other ways
| like connectivity matrix are less general: if you have a lot of
| nodes, and by several orders of magnitude less then N^2 edges,
| then the most of matrix elements will be empty. Moreover it is
| not obvious way, you need to explain it also on top of your
| goal to explain what you are explaining about
| geometry/topology. So if you tried to do it you'd spend all the
| allotted time talking about pros and cons of different
| representations of topology.
|
| I believe that if someone tried to talk about topology while
| using Rust as a language for sample code, he/she would use some
| other representation, because a soup of pointers is a PITA in
| Rust. It is easier to claim that we will be using a
| connectivity matrix, or a Vec of edges, and to explain how it
| works, than to juggle with pointers.
| Const-me wrote:
| I usually keeping these things as indexed meshes:
| std::vector<Vector3> for positions, and
| std::vector<std::array<uint32_t,3>> for the triangles. As a
| nice side effect, the representation is compatible with GPUs,
| matches VRAM layout of the vertex/index buffers.
|
| For some simple algorithms which need adjacency information,
| that's everything needed. For instance, to compute per-vertex
| normals, nothing else is required, create an std::vector for
| the per-vertex accumulators, and iterate over the triangles.
|
| For complicated algorithms which need adjacency information, I
| build special indices over the same data. To find triangles
| connected to specific triangle, a hash map with uint64_t keys
| (two sorted uint32_t vertex IDs in the lower/upper half of the
| integer) and a structure of two uint32_t values (triangle IDs,
| good meshes are guaranteed to have exactly 2 triangles for each
| edge, with opposite winding directions). To find triangles by
| vertex, a multimap from uint32_t vertex to uint32_t triangle.
|
| For algorithms which need to modify these meshes, sometimes I
| generate new meshes instead of modifying old ones. Other times
| I replace erased elements with special values (like UINT_MAX
| for integer indices), append new elements to the end of the
| vectors, and when the algorithm is complete I re-index the mesh
| while removing unused vertices/triangles.
| LorenPechtel wrote:
| If the *only* thing you need is to move along the list then
| pointers are probably the best answer.
|
| However, in my limited experience with such things I have
| always found myself needing both walking around and a big-
| picture list of items. Thus I have always implemented such
| things as a list of elements and storing indexes rather than
| pointers.
| uvdn7 wrote:
| There is this philosophy about software that it needs to be
| redesigned if the workload scales by 10x.
|
| The same applies here. When we are studying a topic, context
| (scale in particular in this case) matters a lot. Just like our
| physical world, and how classic mechanics and quantum mechanics
| are so different.
| Chio wrote:
| This reminds me of an old paper [1] that discuss the performance
| characteristics of different array layouts for searching in
| particular. The conclusion is heavily based on the number of
| cache misses and branch predictor misses that binary search has
| for different array layouts.
|
| Doesn't have much practical application unfortunately since there
| is almost zero support for things like eytzinger layout in most
| standard libraries and sorting an array with a eytzinger layout
| is a bit harder than a non-decreasing layout.
|
| [1] "ARRAY LAYOUTS FOR COMPARISON-BASED SEARCHING", Paul-Virak
| Khuong and Pat Morin,
| https://arxiv.org/ftp/arxiv/papers/1509/1509.05053.pdf
| rurban wrote:
| he should really tested against a deque too, not the two extremes
| only.
| codesnik wrote:
| then he should test it against ringbuffers, IMHO.
| dahart wrote:
| > STL list [...] the mallocs cost will still be greater.
|
| This is a narrow view of the costs of the STL::list container
| class, not of linked lists in general.
|
| Linked lists are at their best when they are _internal storage_ ,
| meaning the links are part of the class being stored, in order to
| prevent unnecessary mallocs. STL::list is an external storage
| container, which automatically compromises some of the potential
| benefits of a linked list. Linked lists are also best when you
| don't malloc to build the list at all, but maintain things
| already in memory. Linked lists are best used in places where
| using vectors is impractical or impossible, like the insides of a
| memory manager.
|
| I don't feel like timing many inserts using STL::list says a lot
| about linked lists at all, and what it does say is mostly
| focusing on the wrong things. Definitely use vector when you can,
| especially if you're just comparing container classes.
| verall wrote:
| STL list is great because it the only STL structure you can
| insert into without potentially invalidating iterators and
| references since it doesn't call resize. If you want a
| performant list-alike, you use a deque.
| guidoism wrote:
| Yeah I was taken aback when they talked about "linked lists"
| and instead of banging out a simple linked list they used an
| STL container that isn't necessarily optimized for the use
| case. It's malloc-heavy and uses full sized pointers instead of
| indices. There's a lot more to the array vs list argument than
| this.
| dundarious wrote:
| Intrusive lists are better, sure, but pointer-jumping will
| still throw away the (absolutely astonishingly large) benefits
| of the cache, unless you're careful. And avoiding pointer-
| jumping is not an automatic win from using intrusive lists --
| you still need to allocate/lay out your stack conscientiously.
| And a very similar argument can be made for bounded arrays as
| an alternative to std::vector.
|
| Also, I only skimmed it, but the article seems to ignore the
| fact that even for an unbounded/growing array like std::vector,
| the growth strategy does not free+malloc/realloc on each
| insertion in practice, as the growth strategy will leave unused
| capacity for future insertions, and in such cases the cost is
| just memmove (for simple types at least). Maybe I missed that
| part, but it seems like an important point worth highlighting.
| dahart wrote:
| > pointer-jumping will throw away the (absolutely
| astonishingly large) benefits of the cache, unless you're
| careful.
|
| Right! Yes, that's part of my point, STL::list isn't being
| careful with cache, or with allocations. Really it just
| rarely makes sense to even compare STL::list to STL::vector
| as if they're otherwise equal choice. Usually the choice is
| (or should be) driven by constraints, not by which has a
| slight perf edge, right? Inside a memory manager, use of a
| vector isn't usually considered a choice. Maybe it's possible
| to build a free page vector, but I think isn't common, and
| people usually pay the costs of pointer chasing on the free
| list because there aren't practical alternatives.
|
| > the <vector> growth strategy does not
| free+malloc/reallocate on each insertion
|
| Yeah very good point. Does STL::list do the same for the
| container of pointers? I don't even know, but maybe it can't,
| and maybe the primary perf advantage of STL::vector over
| STL::list is due to vector's amortized mallocs?
| rhdunn wrote:
| IIRC, the Borland C++ STL implementation made use of
| buckets of consecutively allocated entries so you would
| generally find consecutively inserted items next to each
| other in memory. You can also define your own allocator
| that does something similar.
| dundarious wrote:
| I'd heavily bet against std::list having any kind of "extra
| capacity" logic, as it would have to be some kind of free
| list of Node types -- best leave that to the general
| purpose allocator.
|
| I think the list vs vector comparison is fair, as most
| people are taught to "just use the standard library, don't
| be a hero, don't commit a NIH crime". I have done this
| myself at times, but in fairness, mostly when discussing
| adaptations of existing code, where there were bigger
| structural issues. And it cannot be repeated enough, that
| vector is far better than list, even at prepends or random
| insertions, for a surprisingly large number of elements (it
| was at least thousands of int32-s when I checked it about a
| decade ago). Typically the justification for a list is that
| the workload is prepend/random insert heavy, but in my
| experience there is more often than not a bound on the size
| that strongly favors vector.
| verall wrote:
| > Does STL::list do the same for the container of pointers?
|
| No, if you want a list with amortized malloc, that's a
| std::deque
| jcranberry wrote:
| It seemed like this person was talking about an intrusive
| linked list with an arena allocator of some sort, which isn't
| ideal but still fairly cache friendly.
| travisgriggs wrote:
| It would be interesting to see how this translates to the newer
| Arm/M1 type processor. My experience with timing wisdom over the
| years is that things that are slow at one point (because of
| things like cache misses, etc), shift over time. I find I have to
| frequently recalibrate my expectations of "whats fastest".
| throwaway894345 wrote:
| Genuine question: why would ARM/M1 make cache misses more
| infrequent / faster (or does it just make cache hits slower
| relative to cache misses)? Have cache misses ever been fast
| relative to cache misses such that you would have to rebalance
| performance expectations/intuition?
| travisgriggs wrote:
| To be honest, I don't know. But I do know that the speed at
| which memory moves can alter the game when using traditional
| based "intel" optimization wisdom.
| [deleted]
| dekhn wrote:
| I've been curious about this since I first learned about lists-
| my first "real data structure" (not provided by C). It took me a
| long time to wrap my head around them, but once i did... I was
| armed for a whole range of other more complicated data
| structures. That said, throughout my career, the number of times
| I've used an actual linked list (always double-linked and
| mutable) is quite small, as I had already found that vector was
| much faster for small operations (lists under 100 integral
| items), because, well, Intel optimized for people like me.
| quadcore wrote:
| Thats right. Though in reality, programs behave in _a complex
| way_. You rarely have to insert something in the middle of a list
| in practice. You rarely do random behaviors, at least in my
| field. Let me explain.
|
| In the game industry, we use contiguous-allocated _intrusive_
| free list memory pools. For enemies or projectiles as an example.
| Those things live and die (they are removed from the free list
| and inserted in the "live" list or put back in the free list
| when they die) in such a way the locality is kept good.
|
| Admitedly I dont have sources nor benchmarks and never did. But
| its obvious it at least invalidates author's point in the sense
| that benchmarks gota be done in real life programs.
| devit wrote:
| Linked lists only perform poorly if you iterate them, or
| otherwise access multiple items at once.
|
| If you use them as a single-linked free list they are faster
| than a vector since you only need to fetch a cache line for the
| object rather than a cacheline for the object and one for the
| vector storing free objects.
| pornel wrote:
| Even this doesn't give you optimal locality. Objects in the
| same pool are closer than if they were randomly fragmented from
| a global allocator, but if you're accessing them in the list
| order, you're not accessing adjacent addresses to take
| advantage of memory prefetch. If the pool is large, it may not
| even fit in the cache.
|
| When performance needs to be maximized, games switch to entity
| component systems and switch from arrays-of-structs to structs-
| of-arrays. This enables processing all objects as a vector,
| linearly from start to end, and often without needing to fetch
| any irrelevant bytes that aren't processed in a given pass.
| This sometimes also helps utilize SIMD for data spanning more
| than one entity, which you can't do when using linked lists.
| PaulHoule wrote:
| I got schooled on this topic a while back. I was arguing in a
| discussion that ArrayList was always better than LinkedList in
| Java.
|
| Most of the time it is, but note that ArrayList has to
| occasionally allocate a new array when the list outgrows the
| array inside it, then copy the list.
|
| When the list gets huge, that operation of reallocating and
| copying gets disruptive as it puts a lot of pressure on the
| cache, memory allocation system, etc.
| kllrnohj wrote:
| If the worst case latency of ArrayList is a deal breaker, then
| almost certainly the average case latency of LinkedList is also
| a deal breaker.
|
| You maybe want something like a linked array, but it's
| staggeringly difficult to find a scenario where a Java
| LinkedList or c++ std::list is ever the optimal choice. You
| should pretty much always start with an ArrayList or
| std::vector and go from there if/when it ever turns out to be a
| hotspot in benchmarks or profiling
| kaba0 wrote:
| I believe it corresponds to the traditionally learnt O(n)
| lookup, O(1) insertion/deletion of linked lists, whereas the
| reverse is true of arrays (having to move the items).
|
| Though in practice I find that unless you are often deleting
| elements from the middle, modern CPUs will _really_ prefer
| copying a huge amount of serial data, so an arraylist may still
| be faster all around then LinkedLists. (The CPU will recognize
| you moving values in a given direction and will have the best
| pipeline it can have)
| PaulHoule wrote:
| Most of the time that is right. In fact, there was a
| revolution in how people write query processing systems in
| the 2010s where people realized that the performance of a
| processing pipeline that reads columnar data structures
| straight through is amazing, particularly if you can use SIMD
| instructions.
|
| On the other hand, pointer chasing often isn't as bad as you
| think it might be. That is, modern allocator/garbage
| collectors often end up laying out the parts of a linked list
| in a predictable way such that access is somewhat strided and
| the fetcher is reasonably efficient at traversing the list.
| kllrnohj wrote:
| > On the other hand, pointer chasing often isn't as bad as
| you think it might be.
|
| It kinda really is, though. In addition to cache line
| locality, serial access also benefits from being
| speculatable. The CPU can't very effectively speculate past
| a pointer chase (and on arm little cores it doesn't even
| try), so those become pipeline stalls.
|
| Even if the pointer happened to be close-ish, it's still
| going to end up being a stall more often than not.
|
| And an allocator / GC is only going to lay out a linked
| list in any sort of predictable way if the linked list is
| built up all at once, in which case a linked list is
| obviously not the right data structure anyway ;)
| exyi wrote:
| Thing is that in a pointer heavy environment like Java (or
| Python, JS, C#, even C++ with too much OOP), it does not matter
| that much.
|
| The ArrayList will be a nice flat chunk of memory... of
| pointers to the data, so you'll have to do a lookup for each
| element anyway. The LinkedList will have two lookups still, but
| it's not an order of magnitude anymore. Now it's more of a
| tradeoff between bit slower reads / bit faster updates.
| dbrueck wrote:
| > I was arguing in a discussion that ArrayList was *always
| better*
|
| Tsk tsk. A critical rule for flame wars that also applies to
| mere discussions among common folk is that you should avoid
| using absolute terms, as it gives your opponent an easy
| opening. Instead, couch your statements in vague and wishy
| washy terms like 'usually' and 'often'.
|
| This also helps when your opponent produces a valid
| counterexample - you can petulantly retreat to safer ground
| while grumbling about how of course there are occasional
| exceptions and then, if you wish, you can sidetrack the
| argument into a debate about how often it really happens. From
| there you can feign boredom and exit, think up a snarky, mic-
| drop conclusion, etc.
|
| - As taught in _Raised on the streets of BBSs and USENET_
| lazide wrote:
| True mastery right here.
|
| Senior Architect?
| PaulHoule wrote:
| In this case I not only got schooled but encountered an
| example for myself almost right away.
| sitkack wrote:
| Stop giving away the Dark Arts!
|
| No seriously, once you recognize the components of Rhetorical
| Combat, you can determine if you are going to have a
| civilized discussion, or if the parties will weasel their way
| around for sport or entertainment.
|
| If someone attacks my argumentation with uncharitable takes,
| my discourse with them is over.
|
| I personally would rather arrive that the truth and be wrong,
| than win an argument and let the truth escape.
| dbrueck wrote:
| Well said!
| lern_too_spel wrote:
| ArrayList is still better in your case. Having to do log(n)
| contiguous copies when reallocating is much better than having
| a copying GC copy n live objects that are 5x as large as the
| element by itself or a mark and sweep collector mark n live
| objects.
| munificent wrote:
| The overhead of ArrayList reallocations is no more disruptive
| at small scales than it is at large scales. (Of course, the
| total memory needed at large scales can be disruptive, but
| that's fundamental. If you've got a lot of elements, you need a
| lot of memory for them.)
|
| ArrayLists grow by allocating a new buffer whose size is a
| multiple of the current size. This means that as the buffer
| size gets bigger, the reallocations become less frequent.
|
| The end result is that appending to an ArrayList has constant
| time _amortized_ complexity, even though it will periodically
| do increasingly large copies.
|
| https://en.wikipedia.org/wiki/Amortized_analysis
|
| I bombed an interview once because my interviewers didn't
| understand amortized analysis and I wasn't able to get them to
| understand it.
| oldsecondhand wrote:
| > (Of course, the total memory needed at large scales can be
| disruptive, but that's fundamental. If you've got a lot of
| elements, you need a lot of memory for them.)
|
| But in case of a linked list that large amount of memory
| doesn't have to be contigous, and you don't have to perform a
| lot of copying all at once which kills responsiveness.
| munificent wrote:
| _> But in case of a linked list that large amount of memory
| doesn 't have to be contigous_
|
| True! Though in rare cases where that becomes a problem,
| you are probably better off doing a hybrid solution where
| you store the data in a relatively small number of chunks
| or pages. If you have so much data that you are having
| trouble getting a contiguous allocation, you probably also
| can't afford the overhead of an additional pointer for each
| element, which is what a linked list would give you.
|
| _> you don 't have to perform a lot of copying all at once
| which kills responsiveness._
|
| I believe there are ArrayList implementations that
| distribute the copy across a series of operations to
| mitigate this, but, yes, latency can be an issue for some
| use cases. (In general, though, my experience is that
| people overestimate how long it takes to copy a contiguous
| block of memory.)
| SAI_Peregrinus wrote:
| Big-O notation relies on several simplifying assumptions which
| are wrong in practice. It's not useless, but it's for analyzing
| algorithmic complexity, not for analyzing algorithmic
| performance.
|
| Big-O assumes all "operations" are equally costly. That's not the
| case on real hardware, and pretty much never has been. Some
| instructions take more cycles than others.
|
| Big-O assumes that only asymptotic behavior matters, but real-
| world workloads have finite input sizes.
|
| Etc, etc. An algorithm's complexity is loosely correlated with
| its performance, but the two are not identical.
| devit wrote:
| In practice the difference between constant factors is usually
| between 10 and 10^4, while input size can go up to 10^10 and
| more, so factors of sqrt(n) or higher will usually always
| matter, while factors of log(n) or lower will often not matter,
| and factors in between will depend.
| magicalhippo wrote:
| Indeed. I do think knowing about big-O and keeping it in mind
| is important though.
|
| Yes this loop is fast now with my 1000 items, but what if the
| input grows to 100000 or more?
|
| Keeping it in mind can also help you avoid accidentally writing
| O(n^2) loops or worse. More than once I've been unsure about
| the complexity of a library call, so I check the code and it's
| say O(n) rather than O(1), potentially turning my own O(n) into
| a O(n^2).
| bo1024 wrote:
| At the extreme ends, there are two kinds of slow computations.
|
| 1. A small computation that you perform many, many times.
|
| 2. A very, very large computation.
|
| For #2, big-O can still generally tell most of the story.
| (Example: 100 insertions in the middle of a list with a billion
| elements.) For #1, big-O almost irrelevant, and benchmarking is
| key. (Example: a billion insertions into the middle of
| length-100 lists.) So knowing which situation you're in is
| important.
| TchoBeer wrote:
| >Big-O assumes all "operations" are equally costly. That's not
| the case on real hardware, and pretty much never has been
|
| Assuming that operations take a linear amount of time (i.e.
| multiplying three times takes three times as long as
| multiplying once) this won't affect the asymptotic behavior.
|
| >Big-O assumes that only asymptotic behavior matters, but real-
| world workloads have finite input sizes.
|
| This is definitely something to keep in mind when analyzing
| algorithms, but that does not imply asymptotic complexity is
| not useful when analyzing performance. There are other measures
| (e.g. how an algorithm performs on a random small input, or
| maybe your domain is restricted somewhat) and sometimes those
| measures areore useful than big O, but big O remains useful, it
| just is not the end all be all.
| inetknght wrote:
| > _Assuming that operations take a linear amount of time
| (i.e. multiplying three times takes three times as long as
| multiplying once) this won 't affect the asymptotic
| behavior._
|
| This assumption is demonstrably broken if the first
| multiplication is a cache miss but the other multiplications
| then aren't -- an easy example is when the other two
| multiplications have data on the same cache line as the first
| multiplication's data.
| erk__ wrote:
| That is probably a reason big-O is used, the big-O
| definition which says that they most be upper-bounded by a
| linear multiplier. So even if the second and third
| multiplication is faster it will not change the asymptotic
| behavior.
| wildmanx wrote:
| > Big-O assumes all "operations" are equally costly.
|
| This is a big misconception about "Big-O". It does not "assume"
| anything. It's just not what people think it is.
|
| It's an asymptotic upper bound on counting something. In
| sorting algorithms you count the number of comparisons
| expressed as a function of collection size. In collection
| insertion algorithms on some underlying data structure, it's
| counting some not-very-clearly-defined atomic operations that
| are being executed when inserting an element.
|
| Where the assumptions come from is if you start using the
| notation to give performance comparisons and also start
| assuming things about Big-O that are just not true. But that
| has nothing to do with "Big-O".
|
| There is a family of symbols, called the Landau symbols, of
| which Big-O is only one. There is a lot of misuse of the symbol
| and in many cases what people actually mean is Theta(N) or
| Omega(N).
| ynik wrote:
| Big-O/Theta/etc. are just tools for analyzing functions. But
| it also matters which function you are analyzing.
|
| Typically a program is evaluated in terms of something like
| the "Random-access machine" where every instruction has a
| constant cost. There's a bunch of additional assumptions
| hidden in this machine model!
|
| In the real world, the speed of light and the Bekenstein
| bound conspire to make constant-time random-access to a
| memory of unlimited size impossible. In practice, a random
| memory access takes O(sqrt(N)) time. We like to pretend that
| there's a constant worst-case access time, but that only
| works out because our machines have a limited amount of
| memory -- it's not really appropriate for an asymptotic
| analysis.
|
| So complexity theory based on the "Random-access machine" is
| just measuring a theoretical instruction count that doesn't
| necessarily correspond to the real-world run-time. There's
| other models that get closer, e.g. the "cache-oblivious
| model".
| whatshisface wrote:
| This is a pattern of discussion I see a lot on HN:
|
| "People who believe in X are wrong because A, B, C."
|
| "No, X is actually right, because if you know about these
| obscure parts of X-theory which laypersons never hear about,
| you will see that it addresses A, B and C."
|
| Of course, both these comments are right, because in addition
| to the fact that X-theory does in fullness address those
| issues, few people know how it does.
| Jtsummers wrote:
| This is CS 101 material here, if it's obscure to people in
| the software industry, that speaks poorly of the industry
| and who it hires.
| sitkack wrote:
| It isn't CS 101. You are being overly dismissive and even
| CS people from top schools get this stuff wrong.
|
| The courses that introduce big-O are often the weeder
| courses, they don't aim to education, they aim to flunk
| out the people that might be hard to teach so that CS
| departments can gate keep.
|
| When you have top CS researchers having to give talks to
| remind people that layout matters more than instruction
| selection, the CS as a whole has focused on the wrong
| things.
|
| https://www.youtube.com/watch?v=7g1Acy5eGbE
|
| Figure how to build people up, not tear them down.
| jcranberry wrote:
| After an introductory programming course, the next course
| is data structures which will introduce you to Big O.
| tadfisher wrote:
| Weird, we didn't get into complexity theory until CS 350.
| Before that we mostly focused on logic, data structures,
| and languages (with a bit of computing thrown in). This
| was at Portland State in the late 2000s though.
| bluefirebrand wrote:
| It's stuff that every CS student encounters but probably
| relatively few people who are self taught or do coding
| bootcamps will ever encounter.
|
| Also probably a part of a course many people snooze
| through.
| cgriswald wrote:
| I see it mentioned somewhat frequently by learners on
| 'learn-to-code' platforms when discussing code. Even when
| thinking about it wrongly, it can useful.
| ironmagma wrote:
| People who've only done coding bootcamps probably
| shouldn't sign on to Hacker News and start preaching
| about how Big O is wrong.
| bluefirebrand wrote:
| Sure, but they still get jobs building software is what I
| mean.
| mcguire wrote:
| I don't know when the original article was published, but
| Jon Bentley's book _Programming Pearls_ (IIRC) contains
| essentially this same essay (actually, reversing an
| array) and was published in 1986.
| albedoa wrote:
| How does "both are right" follow from "few people know why
| one is wrong"?
| whatshisface wrote:
| Because by and large, at least in the example, most
| people who espouse X do neglect A, B and C.
| dfee wrote:
| > In collection insertion algorithms on some underlying data
| structure, it's counting some not-very-clearly-defined atomic
| operations that are being executed when inserting an element.
|
| Nailed it. My frustration is that those words are rarely
| mentioned, and that atomic isn't really atomic except in the
| context of the problem statement and solution.
| aeturnum wrote:
| > _This is a big misconception about "Big-O". It does not
| "assume" anything. It's just not what people think it is._
|
| In my experience, we all spend more of our time dealing with
| what people think things are than what they really are. Even
| if reality tends to pop its head up now and then.
|
| I think the root comment is correctly describing "how people
| talk about Big-O" - even though, as you point out, they are
| mischaracterizing it.
|
| I find this is often a more vexing problem than the
| underlying performance questions: how do we find good ways to
| talk about the use (and mis-use) of analysis in a way that
| produces good tools?
| dgb23 wrote:
| Not to mention that it is overemphasized in education.
| Probably because teachers often are somewhat disjointed
| from practice.
|
| Similarly "competitive programming", A&D and coding puzzles
| which I find fun but only tangentially useful, will
| typically completely neglect engineering constraints. The
| shape, size frequency and variations of data can almost
| always be at least estimated in the real world, or simply
| assumed.
| aeturnum wrote:
| I don't remember my education over-emphasized Big-O too
| much - I mostly started thinking about it when I was
| preparing to do interviews at the end of my undergrad
| education. I suspect there's been a back-and-forth
| between industry and schools where industry seeks to weed
| out very weak programmers (i.e. those who fail fizz-buzz,
| people who write accidentally exponential code) and
| schools seek to over-prepare against those easy checks.
|
| Real assessments of performance go far beyond the depth
| and breadth of expertise that most students get in
| undergrad - so it's a fools errand to try and junior
| engineers about concepts like that. Big-O has a lot of
| flaws but I get why it seems so useful to all the groups
| that use it.
| dgb23 wrote:
| Assessment of performance can be practiced and taught in
| the small.
|
| It's really just about making decent estimates, testing
| and some profiling. There's of course potential mastery
| here, specific knowledge and tooling, you can dig down
| almost indefinitely, but the basic motions can be taught
| with simple projects. You don't need Google scale to
| encounter performance problems and potential
| improvements.
|
| I know this because I work on small scale things, and had
| to learn this kind of thing on the job. I can imagine a
| ton of educational projects that teach this.
|
| Complexity analysis and A&D are very useful when you need
| them, but they are just two of several tools.
| WorldMaker wrote:
| Big O-notation is _literally_ "first-order approximation"
| (in a complex polynomial, take the "first-order term",
| which most clearly defines asymptotic behavior, and
| ignore the rest of the terms as details). It's a simple,
| silly name for an extremely useful (didactic) tool. I
| don't think it is teaching that has become disjoint from
| practice, but practice has become disjoint from the
| teaching: if I say "first-order approximation" out loud,
| colloquially people understand it to be "a rough
| estimate" and plan accordingly, but sometimes in practice
| people hear "Big O notation" and don't think "this is a
| rough estimate of just a single term in the equation of
| complexity of the operation".
|
| Similarly the term we use is often "N" and "N" could mean
| anything, and in practice you need to know what "N" you
| are optimizing for/against. That's where the engineering
| constraints fit in. It doesn't matter of you pick an
| algorithm with good Big-O in time (where n represents
| number of operations, for instance) if your are
| constrained in space (memory size; cache size; cache
| locality) and vice versa. Big O notation is an
| approximation with respect to some function and that n
| among a selection of choices of different
| functions/different "ns", that complexity function itself
| can vary a lot based on your trade-offs. (Which also gets
| back into Big O is only one such tool, as well. Sometimes
| you really need to know worst case "Omega notation" and
| not really Big O notation, if your constraints include
| lots of worst case things. And so forth.)
|
| Estimation isn't "destiny": know what you are estimating,
| why you are estimating it, and with respect to what
| constraints you are estimating it. Big O notation is
| "back of the envelope math" for algorithms. It serves
| some great uses, especially in practice, but you need to
| know what you are estimating and why.
| LorenPechtel wrote:
| Sort of.
|
| As you go up the scale the Big-O values are almost always
| dominant. It's very rare to see a situation where you would
| choose the algorithm with the higher value.
|
| However, when two algorithms have the same Big-O there can
| still be a big difference in performance, especially in the
| face of how a cache influences things.
|
| (There are cases where the memory accesses are so important
| that they can make the "bad" approach better. A while back I
| did some time testing and found the Sieve of Eratosthenes
| inferior to brute force because of all the cache misses.)
| bluefirebrand wrote:
| At a certain point your best bet is really to profile the two
| approaches to see which performs better.
|
| But if you are starting out with nothing built and only have
| time to write one, you can't really go wrong by going with
| the one with the better Big O. If it's the same, coin toss I
| guess. :)
| trgn wrote:
| Agreed. I'd go a step further, there's a real-world heuristic
| that this implies.
|
| Initially, prefer to task CPU over memory allocation. Crufty
| allocation generally will always have a real negative impact
| felt by the end-user. A low memory footprint is always a win,
| while going for a (theoretical) fast running time may be effort
| wasted.
| shubb wrote:
| Be careful - many people here hang an entire identity on their
| high status, high paid jobs which were earned by memorising the
| answers to theoretical algorithms questions. It is important to
| their self worth that that stuff is relevant to the real world.
|
| You'll get a similar reaction to if you try to show people who
| won money on crypto art or tesla that they are lucky early
| members of a pyramid scheme.
| mfost wrote:
| > Big-O assumes that only asymptotic behavior matters, but
| real-world workloads have finite input sizes
|
| Well I did have a CS teacher that said that O(log n) is
| basically O(1) because in practice, n usually will fit it in a
| 32bit and log n then is 32 at most :D
|
| It might have been said in jest in part but really it's not
| that far fetched.
| sly010 wrote:
| And similarly, very few algorithms are better than O(n),
| because something as simple as adding 2 numbers can be O(n)
| where n is the size of the number in bits :)
| ouid wrote:
| big O assumes no such thing. big O is just an equivalence
| relation on functions.
| thaumasiotes wrote:
| But big-O is _not_ an equivalence relation on functions,
| because it isn 't an equivalence relation. A big-O
| relationship is not symmetric: if f(x) = x2 and g(x) = x3,
| you can see immediately that f(x) = O( g(x) ), but it is not
| true that g(x) = O( f(x) )
|
| Big-O is a statement about the limit of a function as the
| input goes to infinity. f(x) = O( g(x) ) is the statement
| that the limit (f/g)(x) exists as x goes to infinity. f(x) =
| o( g(x) ) is the stronger statement that the same limit
| exists and is equal to zero.
| Thomashuet wrote:
| > Big-O assumes all "operations" are equally costly. That's not
| the case on real hardware, and pretty much never has been. Some
| instructions take more cycles than others.
|
| No, it only assumes that there is a constant factor between the
| fastest and slowest "operations". It does not matter that one
| instruction can take a thousand times more cycles than another,
| if you have n2 fast instructions and n slow ones, the running
| time will still be dominated by the n2 fast ones for large n.
|
| > Big-O assumes that only asymptotic behavior matters.
|
| Yes, and this is the only simplification that it does.
| dfee wrote:
| Give me a sufficiently large n and I'll give you a
| sufficiently large constant.
| ericpauley wrote:
| False. The whole premise of asymptotic complexity is that
| the constant factor must be finite as n goes to infinity.
| tialaramex wrote:
| Machines don't _do_ infinity. This article isn 't about
| an imaginary computer with an infinitely long paper tape
| from a thought experiment, it's about a real computer,
| just like the ones many HN readers work with every day.
|
| As a result k*N can actually be _bigger_ than N^2 when in
| fact N isn 't "an integer" in a mathematical sense but
| merely a 32-bit machine integer, for example - simply by
| k being more than 4 billion in that case.
| drran wrote:
| Algorithms and programs are different things. An
| implementation of the algorithm is called a program.
| Big-O is used for comparing of algorithms. An algorithm
| can be implemented in different ways. Performance of the
| program can be measured precisely. Different
| implementations of the same algorithm will have different
| performance. When precise information is available,
| assumptions are useless. When precise information is not
| available, at design stage, assumptions are used to
| compare different algorithms.
| tshaddox wrote:
| > This article isn't about an imaginary computer with an
| infinitely long paper tape from a thought experiment,
| it's about a real computer, just like the ones many HN
| readers work with every day.
|
| If you're determined to throw out any concepts which
| technically only apply to theoretical computers with
| unbounded memory, then go all the way. Your actual
| physical computer can trivially iterate through all of
| its possible states in a fixed amount of time. The
| halting problem is trivially solvable for all programs
| that your actual physical computer can execute. Your
| actual physical computer isn't even Turing complete.
| tialaramex wrote:
| > Your actual physical computer can trivially iterate
| through all of its possible states in a fixed amount of
| time.
|
| Nope. You're in an imaginary world again. This universe
| will cease to support computation a _long_ time before it
| would be possible for the computer to try all possible
| states.
| tshaddox wrote:
| Sure, but that's like saying that your computer could
| experience power outages or hardware failures at any
| time. That's true, but we don't normally consider those
| as limitations to the computational capabilities of your
| computer.
| tialaramex wrote:
| It's a difference in kind. The computer _could_
| experience a power outage, it _could_ experience a
| hardware failure, but regardless it and all other real
| computers _will_ cease to operate long before it would be
| able to explore all possible states.
| tshaddox wrote:
| I don't think it's a difference in kind. Given some
| specific physical computer, how would you determine an n
| such that n states are iterable on that computer but n+1
| states are not iterable due to the universe's ability to
| support computation?
| benibela wrote:
| If N is a 32-bit machine integer, then O(N^2) is actually
| O(1)
| rhdunn wrote:
| The idea behind Big-O notation is how the time generally
| varies as you increase the number of items for a given
| algorithm on a given data structure/data set. That is if
| you plot a graph `y=f(x)` where `f(x)` is the time taken to
| perform that operation and x is the number of items you are
| performing it on. You can then match that resulting curve
| to a polynomial or other mathematical expression, and Big-O
| is the dominant term in that expression without any
| associated scale factors (e.g. for 6x^3 + 2x^2 + 7 you have
| an O(n^3) algorithm).
|
| Sure, you can choose a large constant such that numerically
| it is equal to or smaller than O(n^2) for a given n, but as
| you vary n then O(1) should approximate a flat `y=N` line,
| while O(n^2) should approximate a parabola and would result
| in values larger and smaller than N as you vary it.
| bluefirebrand wrote:
| There is something of a bounded limit on how long a single
| operation could possibly take, assuming your hardware isn't
| just plain faulty.
|
| Yes, for the purposes of Big O, we define operations such
| that they aren't simply 1:1 instructions to the hardware,
| but they should be basic commands offered by your
| programming language.
|
| If the basic commands in your language are taking extremely
| high bounded amounts of time, that's a sign your
| programming language is extremely poorly optimized, not
| that Big O isn't useful.
| thfuran wrote:
| A read that hits the network could take a pretty long
| time.
| xigoi wrote:
| That's why, when dealing with network algorithms, you
| analyze the IO complexity in addition to time complexity.
| tshaddox wrote:
| If the large number you give me depends on the n that I
| gave you, then what you gave me isn't a constant.
| mattarm wrote:
| I think that makes sense only for smaller n. At some point
| your "sufficiently large constant" will need to essentially
| be computed from the "worse big-O" algorithm to slow the
| "better big-O" algorithm down enough. E.g. making an O(N)
| as slow as an O(N^2) algorithm would require a sufficiently
| large constant roughly equivalent to N^2, at which point
| you really just have turned the O(N) into O(N^2) in
| practice.
| varajelle wrote:
| See also the "galactic" algorithms:
| https://en.m.wikipedia.org/wiki/Galactic_algorithm
| kevin_thibedeau wrote:
| Smaller N happens a lot in the real world. Sequential
| search can beat binary search for sufficiently small N
| despite being the "worse" choice.
| sitkack wrote:
| Because in Software Engineering, layout matters.
| Computing Machines don't care about asymptotic behavior.
| chongli wrote:
| That's not how constants work in mathematics. You have to
| give the constant first and cannot change it later. That is
| what it means for a quantity to be constant.
| bjourne wrote:
| No, in Big-O notation the magnitude of positive constant
| factors is completely irrelevant.
| mikebenfield wrote:
| The fact that the magnitude of positive constant factors is
| irrelevant doesn't mean it makes any assumptions about the
| cost of operations.
| DoubleFree wrote:
| The quote "Efficiency with algorithms, performance with data
| structures"[1] is very applicable imo.
|
| [1] https://isocpp.org/blog/2014/12/efficiency-with-
| algorithms-p...
| namibj wrote:
| Actually, things like merge-join can benefit from the
| hierarchical aspect of something like a Btree, making not
| only the individual accesses/seeks more efficient, but also
| saving more in the first place
| kadoban wrote:
| You're free to use other compuational models in algorithm
| analysis, which define what costs you're assigning to which
| operations. If you use big-O on top, then the actual numbers
| won't matter, but which operations you count certainly do.
|
| For example you could count only non-cached memory accesses on
| a particular model cpu. See "Idealized Cache Model" from
| https://en.m.wikipedia.org/wiki/Cache-oblivious_algorithm for
| example.
|
| This is part of algorithms analysis that a lot of developers
| skip: these are just tools, there's many models available to
| use with them, or if you want to, just use wall-clock, with all
| of the pain that comes with that.
| 2OEH8eoCRo0 wrote:
| > it's for analyzing algorithmic complexity, not for analyzing
| algorithmic performance.
|
| Everyone seems to forget this. It's more a measure of how an
| algorithm will scale rather than performance.
| bo1024 wrote:
| That's a good way to put it.
| jonny_eh wrote:
| It's still useful for comparing potential performance of
| algorithms with different O(x).
|
| e.g. an O(n) algorithm will most likely outperform an O(n^2)
| algorithm, but two different O(n) algorithms can still
| perform quite differently.
|
| But you're right, it's meant for comparing scaling.
| KptMarchewa wrote:
| Some algorithmic competitions (eg. Polish Olympiad in
| Informatics) go even further, and judge programs not on
| execution time, but on executed instruction count, effectively
| emulating processor with very large amount of RAM.
|
| https://github.com/sio2project/sio2jail/blob/master/src/perf...
| renonce wrote:
| A practical example that counts instructions is EVM. Gas
| usage is counted deterministically to limit computation
| overhead, and smart contracts are designed to optimize away
| every unit of gas since they cost real money.
| stjohnswarts wrote:
| In all these years of c/c++ linked lists have never been my
| bottleneck... It's always good to know of such things though and
| keep them in mind.
| fmajid wrote:
| Branch prediction probably also favors the vector, if not as
| overwhelmingly as the cache locality.
| eof wrote:
| Reminds me of this masterpiece of a rust tutorial; Learning Rust
| With Entirely Too Many Linked Lists - https://rust-
| unofficial.github.io/too-many-lists/
| cesaref wrote:
| It's the usual premature optimisation problem. I'd personally go
| with whichever data structure makes your code easy to write and
| comprehend, then profile, then adjust as necessary.
|
| 99% of code doesn't need to be efficient, but the maintenance
| cost tends to relate to the sheer amount of code and it's
| comprehensibility, and this cost is the one to optimise for, not
| speed.
|
| For the other 1% that you identify with profilers, go with the
| more optimal data structure, and accept the reduction in clarity
| and purpose.
| kaba0 wrote:
| I would wager that getting big O complexity right is absolutely
| not premature optimizations, it is perhaps the only thing one
| should "optimize" upfront.
|
| The very first, biggest impact performance metric is the
| algorithm used -- anything besides that will be meaningless
| given a bad algorithm.
| cesaref wrote:
| Sure, but this article is comparing two data structures which
| have the same big O complexity for the operation, O(N), and
| the comparison is about the relative performance of the two.
|
| My point is that worrying about this for a code path that
| only happens once at startup is silly, but in the main loop
| of a critical performance code path, then sure, go ahead. The
| mistake would be to use vectors all over the place instead of
| lists 'because linked lists are slow' when they have other
| benefits (e.g. cost of insertion, address of elements don't
| change etc) which may adversely affect the readability of the
| surrounding code if you by default use vectors.
|
| Anyhow, just my opinion of course.
| lazide wrote:
| As with anything 'it depends' - if you're writing CRUD
| enterprise code that at most will see several hundred objects
| at a time, but will have to be understood by 100s of cut rate
| contractors over it's lifetime? Go for obvious and hard to
| screw up, over the most efficient algorithm.
|
| Of course someone will misappropriate it and use it as the
| core of some terribly thought out data handling app with
| billions of items, but at least anyone with a clue will be
| able to figure out why it's terrible later.
|
| And if no one with a clue is around, then not like there was
| any better outcome going to happen except by sheer luck
| anyway.
| cesaref wrote:
| Right, and my point is that maintenance is a massive cost
| which is boring, and often overlooked when talking about
| the 'cost' of code. Slow code causing excessive CPU load or
| requiring multiple application servers is one cost, but
| maintenance is another, and the skill is to understand when
| it's appropriate for what.
|
| My default would be to generate maintainable code first,
| and worry about performance when it matters, but a knee-
| jerk 'linked lists are slow so avoid' approach is almost
| always the wrong way of approaching it. Choose the correct
| data structure and algorithm for maintainability, then
| optimise if it's too slow should be the default in my
| opinion.
| tobiasSoftware wrote:
| This article doesn't go over my favorite reason why Linked Lists
| are bad. Their main use case is that you can insert into the
| middle in constant time, right? Well, how do you find the
| insertion point? If your answer is anything algebraic, then I've
| got bad news for you: inserting into the middle might be constant
| time, but getting to the insertion point will be linear time.
|
| Really, the only use case for linked lists is if direct pointers
| to elements are cached somewhere, and in that case you are
| probably using a map anyway. IMO linked lists should be replaced
| with an ordered map for this reason.
| LorenPechtel wrote:
| If you have an unordered list finding the spot is linear time
| anyway.
|
| That being said, the cases where a linked list is better than
| an array are very low these days.
| urthor wrote:
| https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vecto...
|
| From 2012. std::deque does very well.
|
| Suspect the difference is fairly anaemic.
|
| Usually if you're choosing data structures, you pick a "good
| enough choice," (any of the three).
|
| Or, if it matters, you pull out your profiler and pick the
| "exact" right one.
| [deleted]
| [deleted]
| hamstergene wrote:
| I once found code that used vector instead of list, and the
| author had a benchmark exactly like this to defend it.
|
| Except that, the benchmark was storing ints but our production
| code stored std::function closures. Changing the benchmark to
| store a simple struct with two shared_ptrs invalidated it,
| showing that list outperforms vector on as little as 4 elements
| for head&middle insertions.
|
| I think all blog articles about CPU caches could use to repeat
| their benchmarks on something that hides a function call (move
| constructor), an atomic write, and an allocation, just to
| demonstrate how tight the boundaries are.
|
| What is good about sticking with fundamental computer science is
| that it provides pretty strong guarantee about what can and
| cannot happen, while hand-written optimizations are fragile. Even
| if optimization does work today, one year later the next
| maintainer may alter data types, or production data volumes may
| change, and the optimization will start doing the opposite.
| metadaemon wrote:
| The only linked lists I've used in production would be Java's
| LinkedHashMap for preservation of insertion order.
| https://docs.oracle.com/en/java/javase/16/docs/api/java.base...
| gus_massa wrote:
| It would be nice to show the data in the tables as graphics too,
| perhaps log-log so it's easier to see all the points.
|
| In the first table: Benchmark
| Time CPU Iterations
| -------------------------------------------------------------
| BM_ListFind/8 2824 ns 2825 ns 247103
| [...] BM_ListFind/8192 3758778 ns 3758624 ns
| 204 [...]
|
| the last column makes no sense. Is that an error sorting the data
| or I'm misunderstanding what it mean?
| Izkata wrote:
| The benchmark is time-limited, looks like to about 0.75 seconds
| (= time * iterations). It ran the test that many times in that
| duration, each iteration taking on average the amount in the
| time/cpu column.
| karroum wrote:
| I agree plots would be nicer (maybe I'll add them) regarding
| the last column it's the number of iterations, google benchmark
| will make less iterations if individual iterations take more
| time.
| gus_massa wrote:
| Now it makes sense.
| kzrdude wrote:
| Linked lists are often used as a "secondary" structure, i.e
| intrusively linked lists of objects that whose main references
| come from elsewhere. Just wondering, are there any alternative
| solutions to those kinds of cases?
| thinkharderdev wrote:
| Wouldn't that just be a vector of pointers?
| [deleted]
| kzrdude wrote:
| Self-answer but in Linux the "XArray" has been developed and
| maybe that can be an actual answer to my question:
| https://www.kernel.org/doc/html/latest/core-api/xarray.html
| [deleted]
| szastamasta wrote:
| I've done similar benchmarks some time ago for Java with exactly
| same conclusions. Due to the way CPUs reads and caches memory the
| only case for linked lists is doing a lot of in the middle
| inserts and deletes while iterating the list.
|
| Array copying is really optimized on current hardware.
| marginalia_nu wrote:
| The redeeming factor (IMO) is that LinkedList implements a lot
| of useful interfaces: List, Queue AND Deque. If you are doing
| something like a graph traversal algorithm, breadth-first
| search or some relative, it's sometimes a justifiable choice
| for storing nodes-to-be-explored. ArrayDeque is marginally
| faster, but honestly not by much.
| sitkack wrote:
| Solve the problem using the best tools available. Then make
| it fast. Most CSmen over focus on runtime performance.
| Xelbair wrote:
| I found that it is very useful in spatial domain.
|
| For example you have a list of points that define a linestring,
| and have to make sure that no two points are further apart than
| some value. It's really simple to iterate over linked list,
| insert a midpoint into the list, stay at the same step and redo
| the calculations(because p0-midpoint can still be longer than
| some value).
|
| But other than that i don't think i had to do many random
| inserts/removals in non-DB contexts.
| chii wrote:
| > the only case for linked lists is doing a lot of in the
| middle inserts and deletes
|
| i thought that was the point of linked lists: O(1) insertion &
| deletion.
| mauvehaus wrote:
| It depends on who's getting billed for the traversal to the
| point of insertion/deletion:
|
| If all you're doing is "Remove the mth item of the list"
| takes O(m) time to traverse and O(1) to do the removal if
| you're starting from the head.
|
| On the other hand, if you already have the pointer to the
| list element for some other reason, somebody else has already
| been billed for the traversal and the insert or removal is
| O(1).
|
| You see linked lists used a lot in e.g. the kernel where the
| traversal has been paid for to get a pointer to an element
| that has then been used for a bunch of things before a
| deletion or insertion happens.
|
| They also have the advantage that in the face of other
| threads mutating the list, the address of the elements
| remains constant. If you have a pointer ti an element in an
| array, and another thread comes along and does an insertion
| or deletion that moves it, now you have a problem.
|
| Single-threaded performance isn't the only criteria for
| picking a data structure.
| LorenPechtel wrote:
| In the real world it's almost certain that somebody else
| already paid the traversal cost in making the decision of
| what to act on. The only common cases where that doesn't
| apply are removing the head (think queue) and adding the
| tail. The latter case can be handled by keeping a pointer
| to the tail in your control structure.
|
| A queue very well might be best implemented as a linked
| list rather than an array.
| lionkor wrote:
| Yes, but only after finding the element which is O(n) worst
| case
| adwn wrote:
| In intrusively linked lists (the one usually used in
| kernels), you typically already have a pointer to the
| object, and therefore, to its next/prev pointers. For
| example, removing a task from the scheduler's RUN list and
| appending to the WAITING list is O(1), because you already
| have a pointer to the task, because the system's
| architecture is structured in such a way that you don't
| have to traverse the RUN list to find the pointer to the
| task's entry.
| gpderetta wrote:
| Exactly. Linked lists work well for secondary ordering of
| elements.
| waynesonfire wrote:
| linkedlists in java are bad.
|
| one of the benefits of a linkedlist is having the ability to
| remove an element from a list in O(1) by having reference to an
| item that is stored in the list. This is allowed since a linked
| list node can remve itself in constant time. This is a common
| pattern in linked lists used in C code for example.
|
| javas linkedlists don't allow for this benefit. since in java
| you have to perform a search for the node to be removed and pay
| a O(n) penalty on a O(1) operation.
| s17n wrote:
| See also the classic Bjarne Stroustrup talk:
| https://www.youtube.com/watch?v=YQs6IC-vgmo
| moron4hire wrote:
| The point of learning about linked lists is not to actually, you
| know, _write_ a linked list. For one reason, your language of
| choice probably already has one, but also, in the process of
| learning about linked lists, you 're supposed to also learn about
| their drawbacks[0]. No, the point is that there are a lot of
| linked-list-like things in the world, so knowing about how to
| work with linked lists helps you work with those things when you
| encounter them.
|
| [0] Seems there are a lot of problems that stem form Comp Sci
| students skimming the syllabus and not actually reading the
| material.
| robmccoll wrote:
| Yeah, we should teach this to undergrads. If you want high
| performance for a dynamic list, you end up making a lot of
| tradeoffs with tricks like:
|
| - Use blocks of multiple elements per actual list element that
| fit your cache line size. Blocks also have the benefit of
| potentially allowing SIMD processing of your data.
|
| - Allocate blocks out of a vector or some other structure that
| reduces your actual number of allocation calls. Maintain a free
| list threaded through this vector.
|
| - Tombstone list elements in their blocks on removal instead of
| repacking the entire list. This allows for fast deletions and
| fast insertions at specific locations (in that you can always
| insert a new block between existing blocks containing only a
| single element or get lucky and re-use a tombstoned slot).
|
| Note that most of these optimizations trade some memory
| efficiency for speed. This is a common theme in optimization.
| Using more memory, but using it more intelligently such that you
| are potentially accessing less of it and accessing it
| sequentially where possible.
| karmakaze wrote:
| TL;DR - Let me introduce spatial locality and cache.
| idealmedtech wrote:
| I find it's best to write readable, straightforward code at
| first, and when performance really matters, benchmark to find
| places where you can eke out the percentage points that matter.
| Premature optimization can waste valuable hours when you don't
| know what how production workloads will stress your application.
| LorenPechtel wrote:
| This. I always write for readability and only pay attention to
| performance when it's something that's going to be repeated
| often and it matters on the big-O scale. Optimizing beyond that
| should only be done with the profiler to guide you.
| DeathArrow wrote:
| When I was a kid and took programming lessons in high school,
| they taught us about linked lists,using Pascal or C.
|
| Back then, there weren't any list like data structures backed by
| arrays, like List from C# and Vector from C++.
|
| But learning linked lists was a good thing, we also had to learn
| about pointers and how memory is layed out, so we also knew that
| sequential access to memory is faster. Also, learning about stack
| vs heap, CPU caches, made a big difference in how we wrote
| programs and how we continued to write programs 25 years later.
|
| So I think I was lucky starting with Pascal and C, continuing
| with C++ instead of starting with Python or Javascript.
| LorenPechtel wrote:
| My general experience with education is that one is well served
| by knowing things a bit deeper than one actually uses them.
| Going one more layer down in education makes the stuff you
| actually do use make much more sense.
| glitchc wrote:
| A linked list is going to be more costly where objects are simple
| integers and a single array access can load multiple adjacent
| elements. In practice, list nodes are more often than not complex
| objects, where loading a single object will flood the cache
| anyways.
|
| Furthermore, the author is masking the true cost of an array
| resize, which often happens in a running system where a finite
| array is completely full and needs to be resized to append an
| additional element. This is the scenario where linked lists are
| most useful.
| gpderetta wrote:
| Reallocating the backing store for a vector is O(n), exactly
| like the cost of inserting in the middle, so it doesn't change
| anything much.
| eternalban wrote:
| You can also simply have a pointer to the value, so a node is
| just three pointers (prev, val, next) in a fixed sized
| structure. This gets you 2 nodes / CL. Add a fixed sized hash
| of value (key) if you want to search the list without chasing
| the val pointer, and your node still fits in a 64b CL. Pad it
| with 24b (yes, sacrifice a bit of space for performance gain)
| and your nodes will cache align.
|
| Resize point is fair but we still options here. A segmented
| approach for very large collections may also help, with tuning
| knobs of array size / segment. The smallish top level ds
| maintaining segment ptrs will be super hot and very likely ever
| present in L2.
|
| It really all depends on how many items are involved and how
| the data needs to be accessed and used.
| jleyank wrote:
| I did not see whether there is a noticeable (or even measured)
| effect vs load on the cpu. I would thing that cache misses
| increase with load as multiple processes compete for the memory
| resources. Perhaps modern machines can schedule around this but
| it should still be tested.
|
| Or, perhaps, this is saying (again) that one should code then
| tune? Pick data structures that facilitate the design you're
| trying for rather than for theoretical elegance? Chips are cheap
| while developers are not, and having a cleaner, saner design is a
| win. Unless your software price per core is so high that people
| won't license more.
| matthews2 wrote:
| How do you define load on the CPU?
|
| It may use less power as it is spending more time stalled,
| waiting for memory. But it could be still using as much time as
| the OS scheduler is willing to give it.
| corysama wrote:
| I would use this as an interview question just to see if the
| person had ever been taught or given any thought to memory
| caches. "How much slower is it to iterate through a linked list
| vs. an array?" I mostly interviewed fresh-from-school grads. The
| most common answer I got was: 2x.
| LorenPechtel wrote:
| I wouldn't consider this a good question because it changes
| with technology. Rather, ask about the factors that influence
| it.
|
| You can have a 2x difference in main memory performance between
| machines these days.
| corysama wrote:
| I wasn't looking for an exact answer. Just an something that
| indicated they were aware of caches at all. When asked to go
| into detail about their estimate, people who guessed 2x would
| start counting arithmetic operations.
| AtNightWeCode wrote:
| I don't think I have seen a linked list used in production code
| in the last +10 years. Maybe there are some cases where it may be
| practical from a design perspective. Many langs have a list
| collection that one is supposed to use instead.
| Const-me wrote:
| About the search benchmark, caches alone do not explain 2 orders
| of magnitude difference. It's also the prefetcher.
|
| CPU cores have a special functional block which observes
| addresses of cache lines requested from memory, detects
| sequential access pattern, and when detected pre-loads data into
| caches (including L1d) in advance. The RAM access pattern of
| std::vector search benchmark is an awesome use case for that
| thing.
| the_af wrote:
| I don't understand this article at all. The author mentions that:
|
| > _The theorical complexities are:_
|
| > _For list: O(n)_
|
| > _For vector: O(n)_
|
| ... but then goes on to compare running times of list vs vector
| and notices vector is 90 times faster than list for many
| operations, mulls over cache locality and whatnot. Did he
| seriously expect O(n) to give him a way to compare running times?
| Big-O is about asymptotic behavior, not a way to compare running
| times in milliseconds between two implementations.
|
| That is, "how many seconds does this take?" cannot be answered
| with "oh, it's O(N^2)".
|
| The author seems _very_ confused about what he is trying to
| argue.
| tobiasSoftware wrote:
| The author isn't confused, rather that is the point he is
| making.
|
| Often schools teach you to only focus on the big O and ignore
| the constant multiplier. Those same schools then teach vectors
| and linked lists as the two main data structures. They talk
| about the cases where one has an obvious strength over the
| other, such as inserting into the middle, or using an index to
| access an element in the middle. However, they tend to skim
| over scenarios where the big O notation is the same but one has
| an advantage due to the constant multiplier, leading many
| students to come away with the impression that big O notation
| is all that matters.
| the_af wrote:
| > _Often schools teach you to only focus on the big O and
| ignore the constant multiplier_
|
| That's news to me. Which schools teach you that? Where I
| studied CS, algorithmic complexity and Big-O was taught in
| Graph Theory (Discrete Maths), and no attempt was made to
| imply it was about run time in milliseconds.
|
| The problem might be that there's plenty of self-taught
| programmers writing blogs that talk about Big-O without
| understanding what it means, and people who "learn" about it
| from said blogs.
|
| There's no theoretical mismatch with reality here. The only
| confusion might lie in the minds of self-taught programmers.
| [deleted]
| MattPalmer1086 wrote:
| Yes, cache misses are a big factor in algorithm speed. I've been
| working on some search algorithms recently. It's actually faster
| to read more bytes, as long as they're close, and make a better
| quality shift based on that rather than reading fewer bytes and
| making a less informed decision. The cost of reading bytes close
| by is negligible.
| extrapickles wrote:
| Most storage media (DRAM[0], SSD, etc) do reads by pages
| anyways, so processing other bytes in that page is fast as they
| have already been fetched.
|
| [0]: https://www.systemverilog.io/ddr4-basics
| continuational wrote:
| This article makes the classic mistake of assuming linked list =
| mutable doubly linked list.
|
| Immutable, singly linked lists (aka cons lists) are a different
| beast entirely, and don't benchmark well in languages with heap
| fragmentation issues.
| gumby wrote:
| And cdr-coded lists, or sublists, can have vastly improved
| cache performance, especially when you have a transporting GC.
| bjoli wrote:
| Does any implementation updated in the last 25 years use CDR
| coding??
| gumby wrote:
| I don't know -- most implementations on popular
| architectures only have two (low order) bits for tagging
| due to alignment issues, so there may not be room. Might be
| easier in the case of a RISC V with the tagging extension.
|
| Also it would be possible to implement such an approach in
| a C++ list container where you don't need boxing (the
| content type is known).
| Const-me wrote:
| > don't benchmark well in languages with heap fragmentation
| issues.
|
| Microsoft has solved most of these issues on Windows, couple
| decades ago. The feature was introduced in WinXP, and enabled
| by default in Vista and all newer versions:
| https://docs.microsoft.com/en-us/windows/win32/memory/low-fr...
|
| I'm not an expert in Linux but I would be surprised if Linux
| didn't do the same. RAM costs have plummeted. The losses from
| RAM usage overhead of LFH became insignificant compared to the
| issues caused by the fragmentation.
| flaviut wrote:
| To be pedantic, Linux doesn't care about how malloc is
| implemented. That's purely userspace's concern.
|
| But yes, the default glibc allocator does have dedicated
| areas for specific sizes of allocation:
|
| > The normal bins are divided into "small" bins, where each
| chunk is the same size, and "large" bins, where chunks are a
| range of sizes[1]
|
| But fixing heap fragmentation doesn't make linked lists
| suddenly fast. You still have your cache bloated with the
| overhead bytes needed for allocation. List elements can still
| be allocated non-contiguously, giving the prefetcher a bad
| day.
|
| [1]: https://sourceware.org/glibc/wiki/MallocInternals#Arenas
| _and...
___________________________________________________________________
(page generated 2022-06-06 23:02 UTC)