how about having a fixed size of malloced block which is split into the required size of nodes and used this memory for linked list, in this case each two nodes are not far ?.
Does it help ?. Thanks, Sathaiah On Wed, Feb 17, 2010 at 6:12 PM, banu <[email protected]> wrote: > Hi, > I had been thinking about this problem from quite sometime. Linked > lists are good dynamic data structures and solve the main problems > associated with arrays(static memory allocation) > > On the other hand, one of the biggest disadvantages of linked lists is > that their cache utilization is extremely poor. This results mainly > from poor spatial locality because nodes of linked list are allocated > in non-sequential memory locations. So when one accesses a node of > linked list, a single cache line(fixed bunch of bytes) is fetched, and > as the other nodes are present far in memory, the cache line most of > the time will not contain other nodes. So every time a new node is > accessed, the previous cache line has to be flushed and replaced by > new cache line containing new node. This means on every access of node > we pay the cost of reading data from main memory(which is very > expensive) and bringing it into cache > > Main problem is that the poor cache utilization can sometimes result > very bad extremely performance especially if the program is memory > intensive (uses lot of heap memory) > > My question is that are their any other data structures which provide > the benefits of linked lists (using dynamic memory allocation) but are > as efficient as arrays in context of cache utilization? > > Thanks > Varun > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
