{"id":518,"date":"2016-03-01T09:00:47","date_gmt":"2016-03-01T16:00:47","guid":{"rendered":"https:\/\/bornsql.ca\/?p=518"},"modified":"2016-02-23T13:41:33","modified_gmt":"2016-02-23T20:41:33","slug":"lazy-loading","status":"publish","type":"post","link":"https:\/\/bornsql.ca\/blog\/lazy-loading\/","title":{"rendered":"Lazy Loading and Tries"},"content":{"rendered":"

This post has nothing to do with SQL Server, but if you like performance tuning, stick around.<\/p>\n

I learn technology by using it, pushing it to its limits, finding out how it breaks. I jokingly refer to myself as a living edge case because I will do something with your product that you might not have expected.<\/p>\n

(If you’re looking for a beta tester, I’m definitely your man.)<\/em><\/p>\n

By the same token, I write a lot of applications (in C#, my language of choice) to test theories and learn new things.<\/p>\n

I have created a word puzzle game (no, you’ll never see it in the wild) that has as its list of permitted words a dictionary<\/a> of approximately 300,000 English words. The list is a text file in ANSI format and smaller than 3MB.<\/p>\n

The puzzle game works along the lines of the Scrabble\u00ae board game, with a set of random letters assigned to each player.<\/p>\n

The trick for me was to limit the possible words from the main dictionary, based on the current player’s letters, to validate against. Unfortunately, even holding the full dictionary in memory in a List<string>()<\/code> object was very (very) slow to filter. It was taking up to 7 seconds each time the letters changed.<\/p>\n

I wrote to my friend, Andr\u00e9 van der Merwe<\/a>, to ask him for help. My goal was to find all possible words with each letter combination, in the fastest possible way, ordered by longest to shortest. Performance is a feature<\/a>.<\/p>\n

Andr\u00e9 suggested I use a trie<\/a><\/strong> to hold my word list. This is principally how autocomplete algorithms work, where each letter in a word is the root of one or more words starting with that same sequence of letters. The computer reduces the list of possible words by following the path down the tree.<\/p>\n

\"Trie<\/p>\n

(I also call this a radix tree<\/b>, but Andr\u00e9 correctly informed me that it’s not quite the same thing. Radix trees are more compact.)<\/em><\/p>\n

A trie would make my search for words extremely fast because one of the properties of a trie is that each letter has a Boolean value (true<\/em> or false<\/em>) if it is the final letter of a word.<\/p>\n

Unfortunately, every time I switched to a new player in the game, the entire word list had to be loaded into memory to be filtered against. For four players, this needed 250MB of RAM because a trie uses a class for every letter, and my word list was consuming over 60MB.<\/p>\n

I work with data a lot. This is after all a SQL Server blog. I realised I didn’t need the entire dictionary in memory, ever. My players get up to 12 letters to work with, so I could eliminate words longer than that, which meant I could filter the word list before even knowing the player’s letters. What if I filtered the length and the player’s letters at the same time as\u00a0building the possible word list?<\/p>\n

Clearly this was a problem for lazy loading<\/a><\/strong>, a design pattern that says you should only load data into memory when you need it.<\/p>\n

My solution was to read the word list off persisted storage (the hard drive) one word at a time, and if it had 12 letters or less, and could be made up using the letters in the player’s set, only then would it be loaded into that player’s trie.<\/p>\n

Problem solved! Each player’s trie loads in under 30ms off SSD storage and 70ms if the word list is loading off a spinning hard drive. Even better, the memory footprint for each trie is only 12MB. This is still much larger than the 2.7MB of the List<string>()<\/code> object, but a good trade-off with performance.<\/p>\n

For reference, I eventually used this C# implementation<\/a>, which Andr\u00e9 and I adapted.<\/p>\n

What coding performance tricks have you used lately? Let me know on Twitter, at @bornsql<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

This post has nothing to do with SQL Server, but if you like performance tuning, stick around. I learn technology by using it, pushing it to its limits, finding out how it breaks. I jokingly refer to myself as a living edge case because I will do something with your product that you might not… <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"neve_meta_sidebar":"","neve_meta_container":"","neve_meta_enable_content_width":"","neve_meta_content_width":0,"neve_meta_title_alignment":"","neve_meta_author_avatar":"","neve_post_elements_order":"","neve_meta_disable_header":"","neve_meta_disable_footer":"","neve_meta_disable_title":"","_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1],"tags":[89,51,60,90],"class_list":["post-518","post","type-post","status-publish","format-standard","hentry","category-general","tag-c","tag-development","tag-performance","tag-trie"],"yoast_head":"\nLazy Loading and Tries - Born SQL<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/bornsql.ca\/blog\/lazy-loading\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Lazy Loading and Tries - Born SQL\" \/>\n<meta property=\"og:description\" content=\"This post has nothing to do with SQL Server, but if you like performance tuning, stick around. I learn technology by using it, pushing it to its limits, finding out how it breaks. I jokingly refer to myself as a living edge case because I will do something with your product that you might not… \" \/>\n<meta property=\"og:url\" content=\"https:\/\/bornsql.ca\/blog\/lazy-loading\/\" \/>\n<meta property=\"og:site_name\" content=\"Born SQL\" \/>\n<meta property=\"article:published_time\" content=\"2016-03-01T16:00:47+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/bornsql.ca\/wp-content\/uploads\/2016\/02\/400px-Trie_example.png\" \/>\n<meta name=\"author\" content=\"Randolph\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Randolph\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/bornsql.ca\\\/blog\\\/lazy-loading\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/bornsql.ca\\\/blog\\\/lazy-loading\\\/\"},\"author\":{\"name\":\"Randolph\",\"@id\":\"https:\\\/\\\/bornsql.ca\\\/#\\\/schema\\\/person\\\/df20853d6458bc0aca0d5f17202e608d\"},\"headline\":\"Lazy Loading and Tries\",\"datePublished\":\"2016-03-01T16:00:47+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/bornsql.ca\\\/blog\\\/lazy-loading\\\/\"},\"wordCount\":657,\"image\":{\"@id\":\"https:\\\/\\\/bornsql.ca\\\/blog\\\/lazy-loading\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/bornsql.ca\\\/wp-content\\\/uploads\\\/2016\\\/02\\\/400px-Trie_example.png\",\"keywords\":[\"C#\",\"Development\",\"Performance\",\"trie\"],\"articleSection\":[\"General\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/bornsql.ca\\\/blog\\\/lazy-loading\\\/\",\"url\":\"https:\\\/\\\/bornsql.ca\\\/blog\\\/lazy-loading\\\/\",\"name\":\"Lazy Loading and Tries - Born SQL\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/bornsql.ca\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/bornsql.ca\\\/blog\\\/lazy-loading\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/bornsql.ca\\\/blog\\\/lazy-loading\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/bornsql.ca\\\/wp-content\\\/uploads\\\/2016\\\/02\\\/400px-Trie_example.png\",\"datePublished\":\"2016-03-01T16:00:47+00:00\",\"author\":{\"@id\":\"https:\\\/\\\/bornsql.ca\\\/#\\\/schema\\\/person\\\/df20853d6458bc0aca0d5f17202e608d\"},\"breadcrumb\":{\"@id\":\"https:\\\/\\\/bornsql.ca\\\/blog\\\/lazy-loading\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/bornsql.ca\\\/blog\\\/lazy-loading\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/bornsql.ca\\\/blog\\\/lazy-loading\\\/#primaryimage\",\"url\":\"https:\\\/\\\/bornsql.ca\\\/wp-content\\\/uploads\\\/2016\\\/02\\\/400px-Trie_example.png\",\"contentUrl\":\"https:\\\/\\\/bornsql.ca\\\/wp-content\\\/uploads\\\/2016\\\/02\\\/400px-Trie_example.png\",\"width\":400,\"height\":375,\"caption\":\"Trie Example\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/bornsql.ca\\\/blog\\\/lazy-loading\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/bornsql.ca\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Lazy Loading and Tries\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/bornsql.ca\\\/#website\",\"url\":\"https:\\\/\\\/bornsql.ca\\\/\",\"name\":\"Born SQL\",\"description\":\"A blog about the Microsoft Data Platform\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/bornsql.ca\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/bornsql.ca\\\/#\\\/schema\\\/person\\\/df20853d6458bc0aca0d5f17202e608d\",\"name\":\"Randolph\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/e464dca1b55497d15e725afa9728080478c391a7492d0065a7fbeb1d456a1986?s=96&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/e464dca1b55497d15e725afa9728080478c391a7492d0065a7fbeb1d456a1986?s=96&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/e464dca1b55497d15e725afa9728080478c391a7492d0065a7fbeb1d456a1986?s=96&r=g\",\"caption\":\"Randolph\"},\"sameAs\":[\"https:\\\/\\\/bornsql.ca\"],\"url\":\"https:\\\/\\\/bornsql.ca\\\/blog\\\/author\\\/bornsql\\\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Lazy Loading and Tries - Born SQL","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/bornsql.ca\/blog\/lazy-loading\/","og_locale":"en_US","og_type":"article","og_title":"Lazy Loading and Tries - Born SQL","og_description":"This post has nothing to do with SQL Server, but if you like performance tuning, stick around. I learn technology by using it, pushing it to its limits, finding out how it breaks. I jokingly refer to myself as a living edge case because I will do something with your product that you might not… ","og_url":"https:\/\/bornsql.ca\/blog\/lazy-loading\/","og_site_name":"Born SQL","article_published_time":"2016-03-01T16:00:47+00:00","og_image":[{"url":"https:\/\/bornsql.ca\/wp-content\/uploads\/2016\/02\/400px-Trie_example.png","type":"","width":"","height":""}],"author":"Randolph","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Randolph","Est. reading time":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/bornsql.ca\/blog\/lazy-loading\/#article","isPartOf":{"@id":"https:\/\/bornsql.ca\/blog\/lazy-loading\/"},"author":{"name":"Randolph","@id":"https:\/\/bornsql.ca\/#\/schema\/person\/df20853d6458bc0aca0d5f17202e608d"},"headline":"Lazy Loading and Tries","datePublished":"2016-03-01T16:00:47+00:00","mainEntityOfPage":{"@id":"https:\/\/bornsql.ca\/blog\/lazy-loading\/"},"wordCount":657,"image":{"@id":"https:\/\/bornsql.ca\/blog\/lazy-loading\/#primaryimage"},"thumbnailUrl":"https:\/\/bornsql.ca\/wp-content\/uploads\/2016\/02\/400px-Trie_example.png","keywords":["C#","Development","Performance","trie"],"articleSection":["General"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/bornsql.ca\/blog\/lazy-loading\/","url":"https:\/\/bornsql.ca\/blog\/lazy-loading\/","name":"Lazy Loading and Tries - Born SQL","isPartOf":{"@id":"https:\/\/bornsql.ca\/#website"},"primaryImageOfPage":{"@id":"https:\/\/bornsql.ca\/blog\/lazy-loading\/#primaryimage"},"image":{"@id":"https:\/\/bornsql.ca\/blog\/lazy-loading\/#primaryimage"},"thumbnailUrl":"https:\/\/bornsql.ca\/wp-content\/uploads\/2016\/02\/400px-Trie_example.png","datePublished":"2016-03-01T16:00:47+00:00","author":{"@id":"https:\/\/bornsql.ca\/#\/schema\/person\/df20853d6458bc0aca0d5f17202e608d"},"breadcrumb":{"@id":"https:\/\/bornsql.ca\/blog\/lazy-loading\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/bornsql.ca\/blog\/lazy-loading\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/bornsql.ca\/blog\/lazy-loading\/#primaryimage","url":"https:\/\/bornsql.ca\/wp-content\/uploads\/2016\/02\/400px-Trie_example.png","contentUrl":"https:\/\/bornsql.ca\/wp-content\/uploads\/2016\/02\/400px-Trie_example.png","width":400,"height":375,"caption":"Trie Example"},{"@type":"BreadcrumbList","@id":"https:\/\/bornsql.ca\/blog\/lazy-loading\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/bornsql.ca\/"},{"@type":"ListItem","position":2,"name":"Lazy Loading and Tries"}]},{"@type":"WebSite","@id":"https:\/\/bornsql.ca\/#website","url":"https:\/\/bornsql.ca\/","name":"Born SQL","description":"A blog about the Microsoft Data Platform","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/bornsql.ca\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/bornsql.ca\/#\/schema\/person\/df20853d6458bc0aca0d5f17202e608d","name":"Randolph","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/e464dca1b55497d15e725afa9728080478c391a7492d0065a7fbeb1d456a1986?s=96&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/e464dca1b55497d15e725afa9728080478c391a7492d0065a7fbeb1d456a1986?s=96&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/e464dca1b55497d15e725afa9728080478c391a7492d0065a7fbeb1d456a1986?s=96&r=g","caption":"Randolph"},"sameAs":["https:\/\/bornsql.ca"],"url":"https:\/\/bornsql.ca\/blog\/author\/bornsql\/"}]}},"jetpack_featured_media_url":"","jetpack-related-posts":[],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/bornsql.ca\/wp-json\/wp\/v2\/posts\/518","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/bornsql.ca\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/bornsql.ca\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/bornsql.ca\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/bornsql.ca\/wp-json\/wp\/v2\/comments?post=518"}],"version-history":[{"count":0,"href":"https:\/\/bornsql.ca\/wp-json\/wp\/v2\/posts\/518\/revisions"}],"wp:attachment":[{"href":"https:\/\/bornsql.ca\/wp-json\/wp\/v2\/media?parent=518"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/bornsql.ca\/wp-json\/wp\/v2\/categories?post=518"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/bornsql.ca\/wp-json\/wp\/v2\/tags?post=518"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}