How do I modify my software to take advantage of locality of reference?

I know what the definition of LoR is, but I don't know what the mechanics are at a codinglevel to take advantage of it. Are there changes I could make to a program that makes useof linked lists that would take advantage of LoR? Asked by thnkingmachine 58 months ago Similar questions: modify software advantage locality reference Computers > Software Development.

Similar questions: modify software advantage locality reference.

Depends what you're doing, of course. First, be sure that the processing of the linked list needs optimization. Typically, to benefit from LoR, you process an array of elements in order of their location in memory.

If the elements are small enough, two or more can fit on a cache line (CPU optimization) or memory page (RAM optimization). Thus, the delay in fetching one element is also used to fetch one or more subsequent elements. Processing of linked lists is usually non-sequential, so you lose the benefits of LoR.

If there's a way you can restructure your linked list into an array, then that would be taking advantage of LoR. This really only makes sense if you will be processing the data intensively.

Make sure that the elements in the list are allocated near each other Linked lists are not the easiest data structure to ensure LoR with. That said, there are still some things you can do, but the real answer is, as always, it depends. LoR depends not only on how you lay your data out, but also on how you access it.

What you do at a code level depends a lot on what language you're writing in. If it's Java or some other managed language, your hands are really tied since you don't have control over the memory allocation. But you wouldn't be using Java if you really cared about performance optimization at this level anyway, right?

If you are stuck in Java, about the best you can do is make sure that the objects in the list are allocated at close to the same time, and hope that they end up close to one another in memory. Now, assuming you're in C/C++, you can have some real fun. Instead of allocating an object for your list every time you insert one, you could pre-allocate an array of objects up front, and grab one from that array when you need one.

That will insure that a large number of them are arranged out contiguously in memory. If you happen to know how large a list you will need up front, you can actually use an array for the entire linked list and keep a list of indexes instead of using pointers. As fun as all of that is, it's not going to buy you much if you have weird access patterns or drastically change the ordering or contents of your list.

Worrying about LoR makes a lot more sense when you are working with arrays so you have some guarantees about their memory layout. The number one rule for LoR when dealing with (multi-dimensional) arrays is to access them row-major. For a 2-D array, that means processing the elements a row at a time rather than a column at a time, since C (and all C-like languages) lay out their arrays in row major format.

Fortran does it differently, but if you were working in Fortran, well, you'd already know all this. If you are interested in this type of stuff, you should do a several things. First, learn C.

Second, learn how your compiler allocates and lays out memory. Third, learn how to use a profiler -- optimizing code that isn't part of your bottleneck doesn't help anything. While it's generally a lost art, performance optimization can be a lot of fun.

There's nothing like cutting the run time of your code in half through nifty algorithmic tricks. So have fun with it.

To be honest, I don't think you are going to find your answer here, this is probably a mite specific. Would you care to mention what language you are working in, and I will see if I can find you a helpful and friendly forum to ask in?.

1 CleverMonkey! , regarding your answer "What language are you working in? ":I'm working in c/c++.

I understand this is probably a bit of an esoteric question for this forum. I was invited to the forum because I was an amazon customer.... and this was just the question that I've been thinking about recently.... If you have a good forum to recommend, I'd be happy to post there. The general area I'd like to apply this to is CEP/ESP.

You can wikipedia Complex Event Processors / Event Streaming Processor if you want to know more....

CleverMonkey! , regarding your answer "What language are you working in? ":I'm working in c/c++.

I understand this is probably a bit of an esoteric question for this forum. I was invited to the forum because I was an amazon customer.... and this was just the question that I've been thinking about recently.... If you have a good forum to recommend, I'd be happy to post there. The general area I'd like to apply this to is CEP/ESP.

You can wikipedia Complex Event Processors / Event Streaming Processor if you want to know more....

2 crispy, regarding your answer "Depends what you're doing, of course. ":Thanks for that answer. If there is frequent visitation of the elements in the list (to, say, look for a matching key) might it be worthwhile to change the list from a simple list, to a list whose elements are an array?

I suspect the answer is: try it and see.....

Crispy, regarding your answer "Depends what you're doing, of course. ":Thanks for that answer. If there is frequent visitation of the elements in the list (to, say, look for a matching key) might it be worthwhile to change the list from a simple list, to a list whose elements are an array?

I suspect the answer is: try it and see.....

" "Watefall and software development. Is it still being used? How well do you think it works?

" "Where are the market opportunities for Oil & Gas related software development in the European and American market? " "Please recommend a good Centrino 2-based laptop for Software Development and Media Laptop" "What is the best virtual machine software to use to run Linux inside Vista for use as a development server?

Want a venture capitalist to invest on website / software development.

Watefall and software development. Is it still being used? How well do you think it works?

Please recommend a good Centrino 2-based laptop for Software Development and Media Laptop.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.