{"id":5,"date":"2005-09-18T22:35:42","date_gmt":"2005-09-19T02:35:42","guid":{"rendered":"http:\/\/thesmithfam.org\/blog\/?p=5"},"modified":"2019-08-12T07:16:43","modified_gmt":"2019-08-12T13:16:43","slug":"power-of-2-array-sizes","status":"publish","type":"post","link":"https:\/\/thesmithfam.org\/blog\/2005\/09\/18\/power-of-2-array-sizes\/","title":{"rendered":"C: Power of 2 Array Sizes"},"content":{"rendered":"

I just picked up a 10-year old copy of O’Reilly’s Practical C, 3rd Edition<\/b> from the library for some light reading. Mostly, I just wanted to see if I would learn anything (as a guage of my own C proficiency). I’m glad to announce that I learned almost nothing, until, that is, I read page 258, The Power of Powers of 2<\/em>.<\/p>\n

This page is in the section on optimization. Before I go further, I must say that I agree with the author, that when it comes to code optimization: don’t. With that aside, let’s proceed.<\/p>\n

I have seen a lot of C arrays declared and allocated with a power-of-2 size (like 256):<\/p>\n

int *values = (int*)malloc(256);<\/pre>\n
And I never really knew why coders used sizes of 256, instead of 200 or some other more “comfortable” number. I figured that it did something to make the code “better”, but I didn’t know exactly what. Today, I found the answer. Most C compilers will optimize this:<\/p>\n
x = x * 8;<\/pre>\n
Into this:<\/p>\n
x = x < < 3;[\/cpp]\n\nThe left shift operation requires fewer cycles than the multiply operation, so malloc()  can get its job done faster when calculating how many bytes to allocate.\n\nThe fact is also true for accessing elements of multi-dimensional arrays. Take, for example, the following matrix:\n\n[cpp]int matrix[256][256][\/cpp]\n\nWhen accesing an element in this matrix array, say element (12,39), the compiler has to do the following computations:\n\n[cpp]base_address + 12 * 256 * sizeof(int) + 39 * sizeof(int)[\/cpp]\n\nThe 12 * 256 can be optimized to 12 << 8, making each array access a tiny bit faster. In code where this is happening a lot, it may even make a difference.\n\nI guess this also explains why there is no 3-byte integer type, while there are 2-byte and 4-byte integers. And there will likely never be a 6-byte integer either.\n\nAnyway, when it comes to optimization, there is so much voodoo and black magic in play that it's really hard to know what provides the most bang for its buck. I might not even be right on this account either. Please correct me if you know better.\n<\/p>\n","protected":false},"excerpt":{"rendered":"
I just picked up a 10-year old copy of O’Reilly’s Practical C, 3rd Edition from the library for some light reading. Mostly, I just wanted to see if I would learn anything (as a guage of my own C proficiency). I’m glad to announce that I learned almost nothing, until, that is, I read page […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-5","post","type-post","status-publish","format-standard","hentry","category-code-and-cruft"],"_links":{"self":[{"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/posts\/5","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/comments?post=5"}],"version-history":[{"count":9,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/posts\/5\/revisions"}],"predecessor-version":[{"id":1628,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/posts\/5\/revisions\/1628"}],"wp:attachment":[{"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/media?parent=5"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/categories?post=5"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/tags?post=5"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}