Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Linked List Problems (2002) [pdf]

cslibrary.stanford.edu

Post reply on HN
Print view View original

11–20 of 113 posts

Re: Linked List Problems (2002) [pdf]

#11

Post by vernie »

avodonosov wrote: post #6
dgquintas wrote: post #2

"Just say no to linked lists!" https://youtu.be/fHNmRkzxHWs?t=2099

He 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 "neve…

Yes, organizing your data in an array of structures is also bad for performance.

Re: Linked List Problems (2002) [pdf]

#12

Post by xfs »

> 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; inext); // 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.

(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..)

Re: Linked List Problems (2002) [pdf]

#13

Post by SunnySkies »

avodonosov wrote: post #6
dgquintas wrote: post #2

"Just say no to linked lists!" https://youtu.be/fHNmRkzxHWs?t=2099

He 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 "neve…

You'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.

Re: Linked List Problems (2002) [pdf]

#14

Post by jzwinck »

avodonosov wrote: post #6
dgquintas wrote: post #2

"Just say no to linked lists!" https://youtu.be/fHNmRkzxHWs?t=2099

He 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 "neve…

> 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.

Re: Linked List Problems (2002) [pdf]

#15

Post by jnwatson »

herodotus wrote: post #5

One 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…

I recently received this as an interview question.

This is one of those tricks once you know it, you'll remember it forever.

Re: Linked List Problems (2002) [pdf]

#16

Post by sparkie »

avodonosov wrote: post #6
dgquintas wrote: post #2

"Just say no to linked lists!" https://youtu.be/fHNmRkzxHWs?t=2099

He 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 "neve…

>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.

Re: Linked List Problems (2002) [pdf]

#17

Post by avodonosov »

jzwinck wrote: post #14
avodonosov wrote: post #6

Earlier quoted context omitted.

He 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 "neve…

> 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.

If 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.

Re: Linked List Problems (2002) [pdf]

#18

Post by duneroadrunner »

dgquintas wrote: post #2

"Just say no to linked lists!" https://youtu.be/fHNmRkzxHWs?t=2099

The 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-Iterator...

Re: Linked List Problems (2002) [pdf]

#19

Post by pvg »

jnwatson wrote: post #15
herodotus wrote: post #5

One 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…

I recently received this as an interview question. This is one of those tricks once you know it, you'll remember it forever.

Which makes it a fun thing to be aware of but a really terrible interview question. It's been kicking around forever as such, unfortunately.

Re: Linked List Problems (2002) [pdf]

#20

Post by posterboy »

SunnySkies wrote: post #13
avodonosov wrote: post #6

Earlier quoted context omitted.

He 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 "neve…

You'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…

the time complexity of insert etc is superior and a good reason for abstraction on top of an array, I would think.
Post reply on HN