\nOne of the\n\nfive things every Win32 programmer needs to know<\/A>\nis that memory latency\ncan throw your big-O<\/I> computations out the window.\nBack in 2003, I ran into a concrete example of this.\n<\/P>\n \nSomebody started with the algorithm presented in\n\nFast Algorithms for Sorting and Searching Strings<\/I><\/A>\nby\n\nJon L. Bentley<\/A>\nand\n\nRobert Sedgewick<\/A>,\nimplemented it in C#, and compared the performance\nagainst a \nRemember, big-O<\/I> notation hides the constants,\nand those constants can get pretty big.\nWhat’s more, the impact of those constants is critical\nfor normal-sized workloads.\nThe big-O<\/I> notation allows you to compare algorithms\nwhen the data sets become extremely large,\nbut you have to keep the constants in mind\nto see when the balance tips.\n<\/P>\n \nThe central point of my presentation at the PDC was\nthat complexity analysis typically ignores memory bandwidth effects\nand assumes that all memory accesses perform equally.\nThis is rarely true in practice.\nAs we saw, leaving L2 is a big hit on performance,\nand accessing the disk is an even greater hit.\n<\/P>\n \nThe tree doesn’t rebalance,\nso inserting strings in alphabetical order\nwill result in a bad search tree.\n(They do call this out in their paper.)\nTo locate a k<\/I>-character string,\nBentley-Sedgewick traverses at least k<\/I> pointers, usually more.\n(“How much more” depends on how many prefixes are shared.\nMore shared prefixes = more pointers traversed.)\nIt also requires k<\/I>(4p<\/I>) bytes of memory to store that string,\nwhere p<\/I> is the size of a pointer.\nRemember those pesky constants.\nHigh constant factor overhead starts to kill you\nwhen you have large datasets.\n<\/P>\n \nMore on those constants:\nComplexity analysis assumes that\nan add instruction executes in the same amount of time as a memory access.\nThis is not true in practice,\nbut the difference is a bounded constant factor,\nso it can be ignored for big-O<\/I> purposes.\nNote, however, that that constant often exceeds\none million if you take a page fault.\nOne million is a big constant.\n<\/P>\n \nGoing back to memory bandwidth effects:\nAt each node, you access one character and one pointer.\nSo you use only 6 bytes out of a 64-byte cache line.\nYou’re wasting 90% of your bus bandwidth and you will certainly fall out of L2.\n<\/P>\n \nBentley-Sedgewick says that this is beaten out\nby not traversing the entire string being searched for in the case of a miss.\nI.e., their algorithm is tuned for misses<\/I>.\nIf you expect most of your probes to be misses, this can be a win.\n(The entire string is traversed on a hit,\nof course, so there is no gain for hits.)\n<\/P>\n \nNote also that this “cost” for traversing the string on a miss\nis overstated due to memory bandwidth effects.\nThe characters in a string are contiguous,\nso traversing the string costs you only L<\/I>\/64 cache lines,\nwhere L<\/I> is the length of the string,\nand one potential page fault,\nassuming your string is less than 4KB.\nTraversing the tree structure costs you at least L<\/I> cache lines\nand probably more depending on your branching factor,\nas well as L<\/I> potential page faults.\n<\/P>\n \nLet’s look at the testing scenario again.\nThe testing was only on hits,\nso the improved performance on misses was overlooked entirely.\nWhat’s more,\nthe algorithm takes advantage of strings with common prefixes,\nbut the testing scenario used randomly-generated strings,\nwhich generates a data set opposite from the one the algorithm\nwas designed for,\nsince randomly-generated strings are spread out across the problem space\ninstead of being clustered with common prefixes.\n<\/P>\n \nThose are some general remarks; here are some performance notes\nspecific to the CLR.\n \nI don’t know whether it does or not, but\nI would not be surprised if \nNote also that Bentley-Sedgewick’s \nto\n<\/P>\n \n(and similarly in the other branches).\n“This code is short but subtle, and worth careful study.” How very true.\n<\/P>\n \nNote also that if you use their “sleazy hack” of\ncoercing a string to a \nNow go to the summary at the end of the article.\n \nNotice that the article doesn’t claim that ternary trees\nare faster than hashing for successful searches.\nSo if that’s all you’re testing, you’re testing the wrong thing.\nOne of the big benefits of ternary trees\nis the new operations available (4 and 5),\nbut if you’re not going to perform those operations,\nthen you ended up paying for something you don’t use.\n<\/P>\n \nThere are several morals of the story.\n<\/P>\n \nMind you, Bentley and Sedgewick are not morons. They know all this.\n<\/P>\n \n[Typo fixed 11am, thanks Nathan_works and Jachym Kouba.]\n<\/P><\/p>\n","protected":false},"excerpt":{"rendered":" Memory access time changes the math.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-17913","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":" Memory access time changes the math.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/17913","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=17913"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/17913\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=17913"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=17913"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=17913"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}HashTable<\/CODE>, TernaryTree<\/CODE>\nand SortedList<\/CODE>.\nSurprisingly, the hash table won on insertion and retrieval of\ntens of thousands of randomly-generated strings.\nWhy?\n<\/P>\nSystem.String.GetHashCode<\/CODE>\ncaches the hash value in the string,\nwhich would mean that the cost of computing the hash\nis shared by everybody who uses it in a hashing operation.\n(Therefore, if you count the cost incurred only by the algorithm,\nhashing is free.)\ninsert()<\/CODE> function\nstores the object back into the tree in the recursive case.\nMost of the time, the value being stored is the same\nas the value that was already there.\nThis dirties the cache line for no reason\n(forcing memory bandwidth to be wasted on a flush)\nand—particularly\n\npainful for the CLR<\/A>—you hit\nthe\n\nwrite barrier<\/A>\nand end up dirting a whole boatload of\n\ncards<\/A>.\nA very small change avoids this problem:\nChange\n<\/P>\n\n p->eqkid = insert(p->eqkid, ++s); \n<\/PRE>\n
\n Tptr newkid = insert(p->eqkid, ++s);\n if (p->eqkid != newkid) p->eqkid = newkid;\n<\/PRE>\n
Tptr<\/CODE>,\nyou had to have changed the type of eqkid<\/CODE> from\nTptr<\/CODE> to object<\/CODE>.\nThis introduces a CLR type-check into the inner loop.\nCongratulations, you just tubed the inner loop performance.\n<\/P>\n\n
\n