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.
[ Parent
| on HN ]
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!