Archived

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

Boltimus

What's faster? Comparing CHARS or INTS?

Recommended Posts

Hello everyone, I''m doing some analysis on Insertion Sort, and have come across an interesting development. It seems that when I sort large arrays of strings, in comparison to large arrays of 8-digit numbers (ints), the time for sorting the strings is faster than that for the numbers, although both grow a n^2, except that the constant is MUCH smaller for the string comparison. What I''m trying to figure out is if modern Intel processors compare char''s faster than ints, since ints are 32-bit while chars are only 8-bit. I know in previous CS classes I''ve had, the old MIPS architecture we studied compared only two 16-bit words at a time (in it''s ALU) Does the newer processors have an increased capacity to say compare 4 bytes at a time with another 4 bytes? which would be the same as comparing two ints? Thanks!! ~Bolt "All men dream: but not equally. Those who dream by night in the dusty recesses of their minds wake in the day to find that it was vanity: but the dreamers of the day are dangerous men, for they may act their dreams with open eyes, to make it possible." This I did...

Share this post


Link to post
Share on other sites
My first guess would be that you simply have less memory to load and store, when working with strings, and any kind of sort is doing a good deal of memory access, so that would be a potential bottleneck. Decreasing the size of each unit would increase the speed.

As for optimized 4x8-bit simultaneous compares, I could imagine that some compilers and/or processors could do that, but I wouldn''t know well enough to back it up too much. Just a guess.


Most of the greatest evils that man has inflicted upon man have come through people feeling quite certain about something which, in fact, was false.

-Bertrand Russell, Unpopular Essays, "Ideas That Have Harmed Mankind"

Share this post


Link to post
Share on other sites
You are asking for it, so here it comes:

MY CHAR IS FASTER THAN YOUR CHAR!!!

*cough* *cough* sorry, serious answer: maybe bytes being smaller means you can pack more into cache at once, giving less cache misses overall, or something? Cache misses are pure evil these days...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Personally, I refuse to believe your results - I strongly suspect a bug in your code. Could you post the source for whatever test you''re running? How long are the strings that you''re comparing? How are you comparing them? How big are the ints? You mentioned 8 digits, so I''m assuming 32-bits. How do you generate the unsorted test data? Are the strings and ints in the same (relative) unordered state, so that your sort will have to do the same work? Remember that insertion sort actually does less work if all elements are within a short distance of their final resting place.

Share this post


Link to post
Share on other sites