which is faster a 2D char array or a 1D array to char pointers?

Question

I just need to know which array is faster : a 2D char array or a 1D array to char pointers.

for example :

char* name1[]={"Marc", "Jean-Marie", "Paul", ...}
char name2[][11]={"Marc", "Jean-Marie", "Paul", ...}

if I have the same exact code that would sort these arrays which one would finish faster ?

What do you mean by dynamic array? I don't see any dynamic allocation here. — Thomas Jager
– Thomas Jager, Commented Mar 26, 2019 at 4:36
If you're planning on sorting them in place, then name1 would likely be faster as you can swap the pointers. The name2 line would require you to move the entire string, not just the pointers to strings. — Thomas Jager
– Thomas Jager, Commented Mar 26, 2019 at 4:41
Did you try? If you seriously need to speed-optimize something, then there is no way around programming both and measuring. If you only know how to implement one of the two, then go with that first and try whether it really is worth optimizing, seeing that the other one is not necessarily faster. — Yunnosch
– Yunnosch, Commented Mar 26, 2019 at 4:44
yeah I will do that later, but now I just needed a quick answer. Thank you — PotatoGrill
– PotatoGrill, Commented Mar 26, 2019 at 4:48

paddy · Accepted Answer · 2019-03-26 06:37:13Z

3

Sorting the second variant will require string copies using an intermediate buffer or byte-for-byte / block-based swapping. It's likely that this will be "slower" than simply moving pointers.

Conversely, using pointers to actual string literals means only swapping pointers as you sort. So it's likely that this will be "faster".

Furthermore, it's likely that your string literals will be packed closer together in memory by the compiler, which can help cache performance, assuming you actually want to sort a much larger number of strings than 3.

For the example you give, however. It's not completely clear-cut. On a system with larger native types (e.g. pointers, or special SIMD enhancements) it's entirely possible that swapping around strings in the 2D array can be optimized to the point where you can barely measure a difference. Although this is highly dependent on the underlying memory architecture, and whether it cares much about alignment.

A final point is that if you have a very large 2D array, it would need to be allocated either statically or on the heap, as it may not fit on the stack.

And of course, you may only begin to see measurable differences at very large array sizes. Using an example with 3 strings is pretty ridiculous.

edited Mar 26, 2019 at 6:37

answered Mar 26, 2019 at 4:48

paddy

63.7k7 gold badges68 silver badges109 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Antti Haapala Over a year ago

Of course you can allocate a very large 2D array with malloc, even with dynamic dimensions...

paddy Over a year ago

Right, of course. This was written in a hurry, addressing these arrays being declared as outlined in the question. I will include this for the sake of completeness.

Rishikesh Raje · Accepted Answer · 2019-03-26 04:49:41Z

0

Firstly, for such a small number of elements it really does not matter. Both are equally fast.

However when you have a large number of elements in the array, you need to look at cache access.

For name1 you have an array or pointers. The pointers itself point to some other location where the string literals "Marc" Jean-Marie" etc are stored. This may cause issues with caching the arrays properly.

For name2 the strings "Marc" etc are copied into the array. This may be easier for cache. However, you should note that if you have a large array the second approach will cause more use of RAM.

answered Mar 26, 2019 at 4:49

Rishikesh Raje

8,6222 gold badges18 silver badges33 bronze badges

Collectives™ on Stack Overflow

which is faster a 2D char array or a 1D array to char pointers?

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related