News for hackers. Stuff that matters.
Re:Avoiding game crashes related to linked lists by gsg on Monday September 10, 2012 @10:49AM (#4500075)
You forgot insertion and removal, which intrusive lists provide in constant time and vectors do not.

If you can own the objects, linked list (of any kind) is usually not appropriate. The essence of the efficiency of an intrusive linked list is that the same indirection that must point at an object that is not owned is reused to give the list structure. Without this trick, linked lists are not much good.

Re:Avoiding game crashes related to linked lists by phaedrus on Monday September 10, 2012 @11:39AM (#4500325)
Again, you're not getting the point. Constant time != "fast", it just has to do with how the operation scales with N. The point, though counter intuitive, is that the constant time of the list operation is larger than the linear time of the vector operation for many values of N.
Re:Avoiding game crashes related to linked lists by cygx on Monday September 10, 2012 @11:44AM (#4500352)
> The point, though counter intuitive, is that the constant time of the list operation is larger than the linear time of the vector operation for many values of N.

Citation needed. The kernel guys in particular would probably be interested in a faster alternative to intrusive linked lists.

Keep in mind that we're talking about vectors of pointers due to the problem domain (multiple lists of potentially large or polymorphic objects), so using vectors won't really help locality.

Re:Avoiding game crashes related to linked lists by gsg on Monday September 10, 2012 @09:42PM (#4503320)
Given a pointer to an object, remove from an intrusive list is three memory accesses: only tiny vectors will give faster operations than that.

Insertion favors intrusive lists even more: allocation and copy free!