Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

dmatter

Are pointers more efficient?

This topic is 5268 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I''m writing some code that needs to be as fast as possible for its environment in C. I''ve been trying to compromise between speed and memory. At the moment I''m using several dynamic arrays of pointers to structures which store all sorts of information. I have several requirements that I''ve guidelined myself, the system must be dynamic (resizable), fast, and comparitively memory unintensive. The whole reason I chose the current method was because the table of pointers itself is smaller than an array of structures and it doesn''t require a huge contiguous chunk of memory i.e. it can be split up in smaller sized chuncks pointed to by each pointer in the table. However, I was also considering using linked lists with two pointers, one to the next element and one to the previous, its main disadvantage (in my mind) is its spead because I cannot simply call up and index, I have to loop through the list until I find the entry I want. Basically I need to know which is more efficient (following the criteria above), or is there a better option all together? Any help would be greatly appreciated.

Share this post


Link to post
Share on other sites
Advertisement
If you are using dynamic arrays... Then you need to know in advance how many items of data you will have in them... Which in most cases you don''t.

So the main advantage of linked lists is that you can add new items, delete items, etc... very quickly and effeciently without having to shift data around in memory...

In most of my applications, i never need to access a particular index directly. So the fact that i can''t do that is not a problem at all. And i do tend to use linked lists a lot, it is rare for me to use dynamic arrays.

I would suggest you use arrays only when you know exactly how much data you need to store in advance otherwise use linked lists.

Share this post


Link to post
Share on other sites
std::vector is a dynamic array; you can get items by index, and it resizes by itself when necessary. if you know ahead of time the number of elements you want, you can have it reserve that much memory so it doesn''t have to resize (which copies all the elements already in there).

you can use a vector of pointers, so it only has to copy 4 bytes per element instead of the entire structs.

Share this post


Link to post
Share on other sites
quote:

If you are using dynamic arrays... Then you need to know in advance how many items of data you will have in them... Which in most cases you don''t.

So the main advantage of linked lists is that you can add new items, delete items, etc... very quickly and effeciently without having to shift data around in memory...

In most of my applications, i never need to access a particular index directly. So the fact that i can''t do that is not a problem at all. And i do tend to use linked lists a lot, it is rare for me to use dynamic arrays.

I would suggest you use arrays only when you know exactly how much data you need to store in advance otherwise use linked lists.


You''re half right. Dynamic arrays should be used if you need to access a random position in the structure very often. On the other hand, if you add elements to it often you should use a linked list.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You know what all that huge amount of cache on your CPU is for? It''s to compensate for this inefficient coding pattern which is EVERYWHERE even where not needed because people are unfamiliar with the realities of modern architectures:

Stuff *ptr;
for (ptr = start; ptr; ptr=ptr->next)
{
dostuff(ptr);
}

This thing (linked list traversal) is very very inefficent compared to a straight array run (unless you have manually allocated the nodes using some clever pool structure).

Share this post


Link to post
Share on other sites
quote:
Original post by krez
[C++ stuff]

Except that dmatter is using C.

Depending on what properties your data has you might be able to store it, sorted, in a tree. That way the structure can grow and, under good conditions, you should be able to find an element fast than you would with a linked list.


Thanks Salsa!Colin Jeanne | Invader''s Realm
"I forgot I had the Scroll Lock key until a few weeks ago when some asshole program used it. It even used it right" - Conner McCloud

Share this post


Link to post
Share on other sites
quote:
Original post by krez
std::vector is a dynamic array; you can get items by index, and it resizes by itself when necessary. if you know ahead of time the number of elements you want, you can have it reserve that much memory so it doesn''t have to resize (which copies all the elements already in there).


Another neat trick is that if you know ahead of time the number of elements you want, you can use a normal array!

Share this post


Link to post
Share on other sites
You could always go and implement something like std::vector in C.

Maybe you don''t need all the extra functions, and maybe you don''t require completely contiguous use of memory. But you can gain plenty from just using the idea of exponential growth of the container size. Going from a structure like

N nodes -> N nodes -> N nodes -> N nodes

to

N nodes -> N*k nodes -> N*k^2 nodes -> N*k^3 nodes

still provides O(n) space overhead (and the advantage that you can tune that amount as you like, to trade off against speed), and gives you an O(lg n) subscript operator, and probably faster iteration overall. Of course, random insertion will still be O(n). You could ameliorate that by implementing some "balancing" scheme so that each "buffer" is not completely filled, I think. There will be occasional O(n) cases that way, but I think the whole thing will amortize out to O(lg n).

Share this post


Link to post
Share on other sites
Thanks, I''ve now adapted my code for linked lists and I''ve changed some other bits around so there''s no requirement to call up a value by index - Now I''m sure there is an increase in speed

I was wondering whats the best way to free a linked list, given the first element?
Currently I think this works:

for (pointer *ptr = data->first, *nextptr; ptr; ptr = nextptr)
{
nextptr = ptr->next
free (ptr);
}

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!