11 ms·
Linked List Problems (2002) [pdf]
- dgquintas 9y ago"Just say no to linked lists!" https://youtu.be/fHNmRkzxHWs?t=2099 https://youtu.be/fHNmRkzxHWs?t=2099
- deleted 9y ago[deleted]
- SoulMan 9y agoStill, Amazon wouldn't stop asking LinkedList for in every damn interview.
- avodonosov 9y agoHe says because of cache misses due to each element being allocated individually. But then working with references is bad in general? If your vector stores references to objects it's bad? Your object fields point to strings - bad too. Should we ditch Lisp and Java? Note, data should not be continuous to stay in cache. Cache is more like paged virtual memory, it consists of cache lines. Before subscribing to the "never use linked lists" view I would like to see a nontrivial program rewritten from lists and references to the "allocate everything at once" approach and measure the performance. If you want to avoid references and allocate everything in place, it may force your program to do a lot of copying. Also, not only CPU performance matters - programmer performance is important too. So-called "high-level languages" try to optimise this.
- vernie 9y agoYes, organizing your data in an array of structures is also bad for performance.
- tomjakubowski 9y agoDoesn’t this entirely depend on access patterns? If you read one field of all elements all at once, sure, a structure of arrays is probably right. But what if you instead read all fields of one element at once? Isn’t it advantageous to have those fields adjacent in memory with an array of structures?
- SunnySkies 9y agoYou're misunderstanding the advice about contiguous. It's not that it's more likely to stay in cache, but if you're accessing data sequentially it's more likely the data you're going to access next is already in cache. Most (all I've read/looked at) benchmarks in Java have data structures backed by linked lists utterly smashed by things implemented by an array. There was in the last year or two a good c++ talk where a game or game engine changed their storage to be more array like and got roughly a 30% boost in performance. Memory locality is usually king, which is why linked lists are rarely used.
- posterboy 9y agothe time complexity of insert etc is superior and a good reason for abstraction on top of an array, I would think.
- stochastic_monk 9y agoVectors are also usually more memory-efficient, period. A singly-linked list uses a pointer for each element an a doubly-linked uses two, while a vector has constant [a pointer and two integers (size and capacity)] overhead. (Unless the vector was dynamically resized and isn't near capacity.)
- trentmb 9y agoCppCon 2014: Mike Acton "Data-Oriented Design and C++ https://youtu.be/rX0ItVEVjHc https://youtu.be/rX0ItVEVjHc https://en.m.wikipedia.org/wiki/Data-oriented_design https://en.m.wikipedia.org/wiki/Data-oriented_design
- avodonosov 9y ago> if you're accessing data sequentially it's more likely the data you're going to access next is already in cache Why?
- yorwba 9y agoCache prefetching. (https://en.wikipedia.org/wiki/Cache_prefetching https://en.wikipedia.org/wiki/Cache_prefetching) Essentially, many workloads access data sequentially and therefore modern cache architectures have special optimizations to make these memory accesses as fast as possible, by prefetching the next item in the sequence before it is actually needed.
- jzwinck 9y ago> data [needn't] be continuous to stay in cache. Cache is more like paged virtual memory, it consists of cache lines. It sounds like you're saying everything will be OK so long as each chunk of 64 bytes (cache line) is used together. But one page is typically 4 KB, and if you use for example all 64 bytes of one cache line, but only one cache line per page, you will suffer from TLB misses.
- avodonosov 9y agoIf you throw your computer out of window it may break. Why whould I access only 64 bytes per page? I suggest you to delete this comment. We are not discussing VM here, I brought it as an analogy just to say cache lines are independent and need not be contineous.
- sparkie 9y ago>But then working with references is bad in general? If your vector stores references to objects it's bad? Your object fields point to strings - bad too. It's not strictly bad, but it's useful to minimize the number of pointer derefrences you have wherever you can. A non-intrusive linked list will have 2 pointer dereferences to access any bit of data. You'll also have n+1 pointer dereferences to access element n. If you have fixed size small objects, then a vector of values is almost always better than a vector of pointers to the small objects. An intrusive linked list will save you a pointer dereference, but you still have the n dereferences to access element n. >Should we ditch Lisp Lisp's lists model a linked list with chains of cons cells, but there's no hard requirement for them to actually be implemented as linked lists. A typical approach is to implement lists in terms of Bagwell's VLists, which are a kind of middle ground between linked lists and vectors. You have reduced number of pointer dereferences, plus increased cache locality, whilst still being able to log n index, insert, delete, and not require large up-front allocations. >and Java If you subscribe to the "everything is an object" model religiously, then yes, you're probably doing harm. As always, there's no hard rules here and it always depends on your problem and data access requirements. You can usually get performance gains by using memory pools, arrays of structures/primitives, and entity systems instead of inheritance hierarchies.
- jackmott 9y ago>But then working with references is bad in general? If your vector stores references to objects it's bad? If you need speed, it can be yes. Depends on access patterns and size of the object. >Should we ditch Lisp and Java? Java's lack of ability to work with memory in this way made many minecraft fans suffer (and waste money!)
- white-flame 9y agoDependent on various internal arbitrary or intentional decisions, copying garbage collectors can in their normal workings place linked list cells in order in memory. While this does still take more memory than arrays, it can take advantage of the caching & sequential auto prefetch as well.
- pjmlp 9y agoCommon Lisp has value types, it is not all about lists. Likewise Java has primitive types, arrays and eventually will get value types, because they already feel the pressure in FinTech of not having them.
- monocasa 9y agoEh, like anything it depends on your use case. For instance, my current use case is an STM32F, which accesses CCM in a single cycle. And intrusive linked lists are a god send for managing pools in embedded systems without traditional memory management.
- duneroadrunner 9y agoThe problem with trying to substitute lists with vectors is that their iterators behave differently. I.e. vector iterators point to positions rather than elements and are prone to being invalidated. So sometimes it's nice to have a vector that supports iterators that behave like list iterators[1]. [1] shameless plug: https://www.codeproject.com/Articles/1087021/Stable-Iterators-for-Cplusplus-Vectors-and-Why-You https://www.codeproject.com/Articles/1087021/Stable-Iterator...
- saywatnow 9y agoCan you briefly describe how the msevector + ipointer works? I tried to look at the code but dense C++ is not my forte.
- duneroadrunner 9y agoYou mean how it's implemented? Umm, well it's been a while, but basically an ipointer is a proxy for an iterator that is stored internally by the msevector. These "internally stored" iterators are updated when necessary. For example, when insert() or erase() is called. One nice thing about it is that it roughly conforms to the principle of "only pay for what you use". That is, the run-time cost is roughly proportional to the number of ipointers you have and the frequency of operations that modify the size of the vector. One caveat is that this mechanism is not thread safe. But whenever you need to share the vector among threads, you can swap it with a vector that is safe to share[1]. And for those that are into memory safety, there is also a memory-safe vector[2] that supports ipointers. Is this the sort of explanation you're looking for? [1] https://github.com/duneroadrunner/SaferCPlusPlus#nii_vector https://github.com/duneroadrunner/SaferCPlusPlus#nii_vector [2] https://github.com/duneroadrunner/SaferCPlusPlus#ivector https://github.com/duneroadrunner/SaferCPlusPlus#ivector
- saywatnow 9y agoThanks, that's clear enough :-). In hindsight I can't imagine what alternative I was thinking of .. I had some idea you might have put the additional cost in the iterator by maintaining only an epoch counter in the vector, but that's obviously not enough to do the right thing in the presence of insert and erase. Your library looks like a good toolset. While I still find the code pretty impenetrable, the number of tests I can see give me confidence. Bookmarked for reference when I'm using C++ again.
- panic 9y agoC++ folks tend to dislike linked lists because it's awkward to make C++ lists intrusive. The STL list containers store the pointers in a separate allocation from the object itself, so they're slower than they ought to be.
- haeffin 9y agoWhere did you get that? The STL implementations I know definitely don't. See https://github.com/llvm-mirror/libcxx/blob/master/include/list https://github.com/llvm-mirror/libcxx/blob/master/include/li... for an example - __list_node_base contains the pointers, __list_node contains the object and derives from __list_node_base, so allocating the node with object and pointers is one allocation.
- panic 9y agoYeah, that's true for values you're willing to allocate inline. The key advantage of intrusive linked lists is being able to add and remove normally allocated objects without having to construct separate list nodes. The STL does have splice(), but it's awkward -- you always have to keep the object in a list and refer to it using iterators instead of normal references.
- barrkel 9y agoA data structure with the linked list inline is the other way around, e.g.: class Foo { Foo *m_next; Foo *m_next_mru; Foo *m_next_sibling; }; With the STL implementation, only one list can have the item inlined; all the other linked lists need two indirections to get to the next element.
- praptak 9y agoYeah, until you need to remove an element from the middle in constant time - this is sometimes useful for things like the implementation of an LRU cache.
- jackmott 9y agoIf you iterate over the list within an order of magnitude as often as you remove an element from the middle, an array will still be faster despite not having constant time removal, no matter the size of the list. To restate, if you have a workload where you iterate over your collection ~500 times, and remove an element from the middle ~1000 times, an array will usually outperform a linked list on a modern computer, no matter the size of the list. It is not until you do removes/adds far more often, and far from the end of the collection, that the linked list will perform better overall.
- praptak 9y agoThat's why I mentioned the LRU implementation. It does not iterate over the list, only adds elements to the front, deletes from the back and moves from the middle to the front. Refs to nodes are stored in a map, so iteration is not necessary to find an element.
- winstonewert 9y agoBut how do you find the element to be moved from the middle if not by iterating over the list?
- baddox 9y agoThe commenter mentions that in the last sentence. There is some separate data structure that also has references to nodes in the middle of the linked list.
- winstonewert 9y agoOy! I can't believe I missed that.
- rayiner 9y agoLook in the Linux kernel to see how often linked lists are used. The list of a process’s memory mapping are, for example, maintained as linked list in parallel with a balanced tree. Lots of queues are maintained as linked lists. Free slabs in the slab allocator are kept in a linked list. The list goes on.
- jokoon 9y agoStill wondering why they are being taught in programming courses. Although they are so many things that are taught, that should never be used in the real world.
- lucio 9y agoWhat is LISP
- delta1 9y agoIn case you're serious, and too lazy to google it... [1] LISP is a family of programming languages. [1] https://www.google.com/search?q=LISP https://www.google.com/search?q=LISP
- lucio 9y agoIt was sort of a Jeopardy response. I'm sorry if it was too opaque. The OP's article just brought LISP into my mind.
- herodotus 9y agoOne of my all-time favourites is this: suppose you have a linked list that eventually cycles: that is, the link of one of the nodes in the list points to a previous node in the list, but not necessarily the first node. Write a function to compute the cycle length of the cycle. Now if it was just a simple circular list, this would be trivial: set a pointer to a node, and move another pointer a node at a time until the two pointers meet. However, this list has an initial sequence of nodes of unknown length that is not in the cycle. So the trick is really to find a node that is guaranteed to be in the cycle. A nice way to do this is to start with two pointers to the head to the list, and then advance one by a single node at a time, and the other by two nodes at a time. It is easy to see that they will eventually meet on the cycle. Once that happens, it is easy to count the cycle length. Now suppose you are running a casino and you are using a random number generator. For any given seed, the generator will eventually cycle, but not necessarily to the seed. You can compute the cycle lengths for a given seed with two variables by analogy with the linked list solution stated above.
- avodonosov 9y ago> It is easy to see that they will eventually meet on the cycle. Not easy for me, but thanks for the algorithm, maybe I will find time and energy to understand and believe. Why by two at a time and not by 3?
- RomanPushkin 9y ago3 will also work. People pick 2 intuitively, and it minimizes the overall runtime of the algorithm. (google "Proof of Floyd's Cycle Chasing" for details)
- xfs 9y ago> 7. Build — Local References struct node* BuildWithLocalRef() { struct node* head = NULL; struct node** lastPtrRef= &head; // Start out pointing to the head pointer int i; for (i=1; i<6; i++) { Push(lastPtrRef, i); // Add node at the last pointer in the list lastPtrRef= &((*lastPtrRef)->next); // Advance to point to the new last pointer } // head == {1, 2, 3, 4, 5}; return(head); } > This technique is short, but the inside of the loop is scary. This technique is rarely used, but it's a good way to see if you really understand pointers. > This technique is never required to solve a linked list problem, but it will be one of the alternative solutions presented for some of the advanced problems. The code is shorter this way, but the performance is probably not any better. This is what Linus Torvalds called "good taste" code and used in Linux kernel. There was some argument about it though: https://news.ycombinator.com/item?id=5030845 https://news.ycombinator.com/item?id=5030845. (Incidentally, I found Nginx is written in the same style recently as I read it - manual linked list manipulation with this double pointer technique everywhere..)
- doiwin 9y agoI have been coding for decades now and never had a use case for a linked list.
- AzzieElbab 9y agoI use lists daily. Why not? It is a stack or queue, if you reverse it
- abhimt 9y agoFor other data structures, refer http://www.techiedelight.com/list-of-problems/ http://www.techiedelight.com/list-of-problems/
- throwaway7645 9y agoI work with traditional RDBMS & and old hierarchical linked-list DB. The linked-list has great performance with super speedy Fortran, but it is a major pain to retrieve any information. Having to write complicated pointer commands is tedious at best. Select * is such a luxury.
- darepublic 9y agoI remember solving these in my spare time while bored at my first internship as a developer. Good memories