Re:On C Linked Lists (Profiling and Optimizing)
by gsg on Monday December 13, 2010 @01:01AM
(#1999532)
The C-style linked lists that TFA discusses don't involve any dynamic allocation. They're intrusive structures that link locations together, not containers that are responsible for memory ownership and management.
Intrusive data structures are actually very malloc friendly because you can include multiple lists in structures that are allocated sequentially, and insert/remove at will without any allocation or deallocation whatsoever. This is of course why C programmers use linked lists heavily.
("realloc is scary"? Really?)
Re:On C Linked Lists (Profiling and Optimizing)
by RodgerTheGreat on Sunday December 12, 2010 @02:18PM
(#1997710)
If those CS students pay attention in their algorithms class, they'll learn that the amortized cost of insertions and removals at the end of a load-based resizable array is still constant anyway. As you say, the overhead of a malloc tremendously dominates a few instruction's worth of logic for capacity checks.
At very large sizes, deletions from the interior can be painful, but at very large sizes you need to be customizing for performance (if that matters) anyways. Instead of deleting, for instance, you can invalidate, and then amortize the memcpy across many deletions; a straightforward time/space tradeoff.
The big problem I have with "performant" linked lists is that malloc is death to performance. The single biggest profiler payoffs I've ever gotten --- order of magnitude improvements --- have been from getting rid of calls to malloc. Yes, you can custom-alloc a linked list, but you're then getting to a place where lists and vectors are starting to converge on each other.
I think C programmers use linked lists instead of "vectors" because realloc resizing is scary, and because every CS student learns linked-lists in their first month of class.