Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
I think linked data structures are very useful, but we seem to have forgotten the overhead involved in using object headers and pointers for explicit ordering.
2 views
Skip to first unread message
Casey Hawthorne
Nov 19, 2009, 5:51:12 PM11/19/09
to
I think linked data structures are very useful, but we seem to have
forgotten the overhead involved in using object headers and pointers
for explicit ordering.
Arrays, use implicit ordering, and without the overhead of object
headers and pointers, quite a few more elements of your data structure
can fit into a cache line. (That is, the good old memory hiearchy.)
--
Regards,
Casey
forgotten the overhead involved in using object headers and pointers
for explicit ordering.
Arrays, use implicit ordering, and without the overhead of object
headers and pointers, quite a few more elements of your data structure
can fit into a cache line. (That is, the good old memory hiearchy.)
--
Regards,
Casey
David Formosa (aka ? the Platypus)
Jan 6, 2010, 12:17:45 AM1/6/10
to
On Thu, 19 Nov 2009 14:51:12 -0800, Casey Hawthorne
<caseyhHA...@istar.ca> wrote:
> I think linked data structures are very useful, but we seem to have
> forgotten the overhead involved in using object headers and pointers
> for explicit ordering.
<caseyhHA...@istar.ca> wrote:
> I think linked data structures are very useful, but we seem to have
> forgotten the overhead involved in using object headers and pointers
> for explicit ordering.
Who is we?
> Arrays, use implicit ordering, and without the overhead of object
> headers and pointers, quite a few more elements of your data structure
> can fit into a cache line. (That is, the good old memory hiearchy.)
Array's vs Lists are (as most things) a trade off. For example
inserting an item into a list is O(1) while into an array is O(N).
Also lists can be handled in a imutable fashon while arrays tend to
require mutable memory.
0 new messages