Imagine your shopping at a different supermarket from normal.\nYou notice that baked beans are 3p per tin cheaper than you’re use to.\nThe news had a story about supermarket price wars on basic goods recently.\nIt’s a bit out of your way but if you switch supermarkets you could save money on beans each month!<\/p>\n\n\n\n
Does that sound familiar?\nNo, probably not.\nSaving 3p on a tin of beans is unlikely to be worth it unless you eat a lot<\/strong> of beans.\nIf the supermarket is out of your way then you might end up spending more money on getting there.\nIt might make sense if you noticed the other supermarket sells steak or bottles of wine at half price.\nOtherwise it’s better to look at the overall cost for a trolley and decide based on that.<\/p>\n\n\n\n Optimisation is a bit like this.\nThere are a few simple ways you can save a fraction here and there.\nThere are even automated ways to detect those situations.\nWhile making your code a few percent faster is nice wouldn’t it be better to make it\nmany times faster<\/a>.<\/p>\n\n\n\n This will trigger a warning because, as Does this really make a difference? I can guess but let’s have a look. It does, pre-allocating space can be 2.5 times faster<\/a>. Or maybe 4.3 times faster<\/a> or 1.5 times faster<\/a>. So yes, it’s faster but details matters. The smaller loops show a greater speed increase. It matters more when you add 10 numbers and less add 1000 numbers. However remember that adding 10 numbers is going to fast<\/em> anyway, there’s only 10 of them. Dealing with 1000 things is where you’re more likely to notice the difference but there the speed is more similar. All of these have been dealing with some of the simplest possible loops. What if they were slightly more complicated? Then pre-allocating space is only 1.1 times faster<\/a>.<\/p>\n\n\n\n It’s not that much<\/em> faster, it looks more complicated and it’s has more room for bugs:<\/p>\n\n\n\n And if you do<\/em> make a mistake it won’t break it will just silently slow down.\nIn some ways that’s worse because it’s unlikely to be noticed and fixed.<\/p>\n\n\n\n I suppose the worst situation for you code is when\nyou are adding, say, 10 numbers to a new array but you’re doing that hundreds of times.\nHowever, you can do even better than using To my mind That way everyone else can write something simple and automatically get the benefit:<\/p>\n\n\n\n This is just as fast<\/a> as pre-allocating the list manually. It can also be easily repurposed to store only even numbers, or string representations of the numbers, or whatever you want to calculate. As it’s something discrete it’s easy to write unit tests for so should be more reliable. Your team will<\/em> have to learn another set of library functions and what to expect from them. That’s a cost that comes with any new library whether you write it yourself or not.<\/p>\n\n\n\n Sometimes you see advice saying to prefer pre-increment operators to get the best performance.<\/p>\n\n\n\n So the first loop is faster than the second<\/a> but\ndid you notice anything special about the test?\nI had to switch the optimisation off.\nWith optimisation switched on the both loops are the same<\/a>.\nIndeed with a more typical loop:<\/p>\n\n\n\n It doesn’t even matter if you don’t use optimisation.\nAgain, both loops are the same<\/a>.\nYou’ll also find if you do anything other than the most basic calculations which operator you use\nlargely doesn’t matter<\/a>.<\/p>\n\n\n\n So technically pre-increment operators can be faster than post-increment operators but\nin practice it hardly ever seems to be the case.\nIt may be that this use<\/em> to matter with older compilers but not today.<\/p>\n\n\n\n Really I have more of a problem with doing something to a value and<\/em> using a value at the same time. If you can separate incrementing the value<\/em> from using the value<\/em> then it’s generally easier to understand what the code is doing. There are less likely to be edge cases that you miss. For me I’d prefer a single increment operator Another idea is that the cost of function calls can add up. People might encourage you to duplicate code or specifically inline functions to avoid this. We can take a simple example of squaring a number. If you do it directly your code will be scattered with Some of these techniques do make for faster code and some don’t.\nFor some of them it matters what optimisation you use, perhaps which compiler as well.\nHowever I’d argue that all of the are relatively<\/em> small gains.\nThey’re small details that are easy to teach, easy to put in a tips & tricks list, and\neasy to write automatic checkers for.<\/p>\n\n\n\n What’s harder to teach is where to get big<\/em> performance improvements.\nGenerally speaking this comes down:<\/p>\n\n\n\n I’ve said it before<\/a> and\nI’ll say it again, the right algorithm can make a huge difference.\nThese can<\/em> be complicated but they don’t have to be.\nBinary search is much faster<\/em><\/a> than linear search.\nHere that’s 8.5 times faster, the biggest performance difference so far, and it’s not a huge example.\nWith a bigger example it gets even more significant,\n54 times faster<\/a>!\nHowever it’s not as simple as using it everywhere.\nFor small lists linear can be faster<\/a>.<\/p>\n\n\n\n I’ve talked about organising your data<\/a> before. At the time I wasn’t impressed by the book but saw that the technique could work. I looked at an example particle system<\/a> where I kept related data together. Again it has a speed up an order of magnitude greater than the little<\/em> ones we discussed earlier. Data that isn’t useful to the calculations at hand can clog up the CPU cache<\/a> and cause more cache misses. It can also help you concentrate on doing only the work that you need to do, separate active and inactive data.<\/p>\n\n\n\n If you are using libraries to do some of your work you might want to investigate alternatives.\nLets consider a fairly common activity, parsing JSON<\/a>.\nFortunately for me someone else has already\nlooked at the numbers<\/a>.\nThe look at 43 libraries from ArduinoJson<\/a>\nall the way to YAJL<\/a>.<\/p>\n\n\n\n There’s a factor of about 140 times between the fastest and slowest.\nPersonally I’m use to using Nlohmann\/json<\/a>\nwhich turns out to be middle of the road.\nIf my project was slow switching to RapidJSON<\/a>\nmight be the way to go.\n(gason<\/a> is the same speed but a different language.)<\/p>\n\n\n\n Are you doing calculations multiple times when you could get away with doing them once? Caching previous work and then re-using it later trades memory for time. I once inherited a project where potentially thousands of tasks where being performed but each triggered the loading and saving of one of dozens of files. That meant a single file might be loaded and saved 100 times on average. Re-organising the code allowed me to load one file, perform 100 tasks and then save the file. It was a massive speedup.<\/p>\n\n\n\n One of the most powerful options is just doing less work.\nLook at what the task actually requires.\nIf it was “List the top 10 items in order cost”.\nYou might total up the cost of every item, sort all the costs and take the first 10.\nThat’s certainly the obvious way to do it.\nHowever, with the right algorithm, you could start sorting all the costs and then stop once you had the first 10.\nThe order of the rest of them doesn’t matter.<\/p>\n\n\n\n There are lots of ways you can improve the performance of code.\nYou might think it’s good to do them all.\nSurely fast code is good code?\nI’d say: clear, readable, flexible and functional code are all more important than just being fast.\nIf you do need<\/em> code that is faster the first thing to do is almost always to \nprofile<\/a> it.\nOnce you know what parts of your code are slow you know where to focus your attention.\nYou get a bigger impact speeding up slow code than speeding up something that is already fast.\nStart by looking for ways to save a lot<\/em> of time rather than a little<\/em>.\nWe usually have limited time for development.\nIt’s not a questions of “How fast can this code possibly be?” but “How fast does this code need to be?”<\/p>\n","protected":false},"excerpt":{"rendered":" Imagine your shopping at a different supermarket from normal. You notice that baked beans are 3p per tin cheaper than you’re use to. The news had a story about supermarket price wars on basic goods recently. It’s a bit out of your way but if you switch supermarkets you could save money on beans each […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[1],"tags":[22,7,18],"class_list":["post-330","post","type-post","status-publish","format-standard","hentry","category-general","tag-algorithms","tag-performance","tag-tools"],"_links":{"self":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts\/330","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/comments?post=330"}],"version-history":[{"count":6,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts\/330\/revisions"}],"predecessor-version":[{"id":353,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts\/330\/revisions\/353"}],"wp:attachment":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/media?parent=330"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/categories?post=330"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/tags?post=330"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}Inefficient vector operations<\/h2>\n\n\n\n
clang-tidy<\/code><\/a>\nis a static analysis tool that can perform all sorts of checks on your code.\nOne of them looks for\ninefficient vector operations<\/a>.\nLets say you want a list of numbers:<\/p>\n\n\n\n std::vector<uint32_t> values;\n for (uint32_t i = 0; i < count; i++) {\n values.push_back(i);\n }<\/pre><\/div>\n\n\n\nvalues<\/code> gradually expands,\nit could trigger multiple memory allocations and copies.\nIf instead you pre-allocate the list then only a single allocation is required:<\/p>\n\n\n\n std::vector<uint32_t> values;\n values.reserve(count);\n for (uint32_t i = 0; i < count; i++) {\n values.push_back(i);\n }<\/pre><\/div>\n\n\n\n\n
reserve<\/code>.<\/li>\n\n\n\nreserve<\/code>.<\/li>\n<\/ul>\n\n\n\nreserve<\/code> by\nthinking about the algorithm<\/a>.<\/p>\n\n\n\nreserve<\/code> is best used when you’re writing library functions that can get re-used everywhere:<\/p>\n\n\n\ntemplate <typename T, typename Generator>\nvoid append_n(std::vector<T>& values, size_t count, Generator generator) {\n values.reserve(values.size() + count);\n for (size_t i = 0; i < count; i++) {\n values.push_back(generator(i));\n }\n}<\/pre><\/div>\n\n\n\n std::vector<uint32_t> values;\n append_n(values, count, [](const int i){ return i; });<\/pre><\/div>\n\n\n\nPre-increment vs post-increment<\/h2>\n\n\n\n
\/\/ First increment and then use the new value.\n uint32_t preTotal = 0;\n for (uint32_t i = 0; i < s_Count;) {\n pretotal += ++i;\n }\n \/\/ Store the old value, increment, and then use the old value.\n uint32_t postTotal = 0;\n for (uint32_t i = 0; i < s_Count;) {\n postTotal += i++;\n }<\/pre><\/div>\n\n\n\n uint32_t total = 0;\n for (uint32_t i = 0; i < s_Count; i++) {\n total += i;\n }<\/pre><\/div>\n\n\n\ni++<\/code> that had the same behaviour as i += 1<\/code>. That way we don’t have to worry about specific pre and post increment behaviours. Unfortunately I don’t get to re-design C++.<\/p>\n\n\n\nFunction calls<\/h2>\n\n\n\n
value * value<\/code>. If you do it via function call you’ll have Square(value)<\/code>. What does the profiler say? Direct usage is about 10% faster than calling a function<\/a>. Interesting inlining the function doesn’t seem to help. Maybe that’s because I had to switch off optimisation again. With optimisation they are all neck and neck<\/a>.<\/p>\n\n\n\nLittle vs big<\/h2>\n\n\n\n
\n
xychart-beta horizontal\n\nx-axis [\"gason\", \"RapidJSON\", \"RapidJSON_Insitu\", \"sajson\", \"ujson4c\", \"RapidJSON_AutoUTF\", \"RapidJSON_FullPrec\", \"Scheredom json.h\", \"mikeando\/FastJson\", \"cJSON\", \"ujson\", \"taocpp\/json\", \"udp\/json-parser\", \"V8\", \"ccan\/json\", \"Nlohmann\", \"SimpleJSON\", \"Configuru\", \"jsoncons\", \"Parson\", \"dropbox\/json11\", \"JVar\", \"YAJL\", \"Vinenthz\/libjson\", \"Jansson\", \"Qt\", \"C++ REST SDK\", \"json-c\", \"PicoJSON\", \"Jzon\", \"JsonCpp\", \"POCO\", \"hjiang\/JSON++\", \"tunnuz\/JSON++\", \"JsonBox\", \"jsmn\", \"nbsdx_SimpleJSON\", \"ArduinoJson\", \"CAJUN\"]\ny-axis \"Parsing time (ms)\" 0 --> 1200\nbar [8, 8, 8, 9, 9, 16, 16, 17, 19, 25, 37, 41, 47, 53, 60, 72, 79, 81, 89, 90, 94, 94, 103, 107, 112, 125, 134, 135, 140, 149, 166, 219, 224, 317, 341, 395, 486, 568, 1133]<\/pre><\/div>\n\n\n\n
In the end<\/h2>\n\n\n\n