{"id":1456,"date":"2022-05-08T21:21:51","date_gmt":"2022-05-08T13:21:51","guid":{"rendered":"https:\/\/markjohntaylor.com\/blog\/wordpress\/?p=1456"},"modified":"2023-10-17T21:51:00","modified_gmt":"2023-10-17T13:51:00","slug":"awesome-swiss-tables","status":"publish","type":"post","link":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/2022\/05\/08\/awesome-swiss-tables\/","title":{"rendered":"Awesome Swiss Tables"},"content":{"rendered":"\n<p>The basic idea is <a href=\"https:\/\/en.wikipedia.org\/wiki\/Open_addressing\">open addressing<\/a>, but without any redirections (thus making Swiss tables very memory efficient). Also, Swiss tables store a densely packed array of metadata with each entry consisting of 1 byte (which makes the metadata table easier to fit into the CPU cache, as opposed to, say, metadata of pointers of 8 bytes), sort of like UNIX file system inodes and bit maps (see OSTEP: Chapter 40 File System Implementation). Thus, we can use this compact metadata to determine if an entry in the table is present, empty, or deleted by using the single control bit and the 7-bit H2 hash (see the details at <a href=\"https:\/\/abseil.io\/about\/design\/swisstables\">https:\/\/abseil.io\/about\/design\/swisstables<\/a>).<\/p>\n\n\n\n<p>And there&#8217;s an excellent video about it on <a href=\"https:\/\/www.youtube.com\/watch?v=ncHmEUmJZf4\">YouTube<\/a>.<\/p>\n\n\n\n<p>Finally, let&#8217;s see the performance differences on the <a href=\"https:\/\/github.com\/How-u-doing\/DataStructures\/tree\/master\/Searching\">counting words<\/a> benchmark.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" width=\"1024\" height=\"492\" src=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2022\/05\/image-1024x492.png\" alt=\"\" class=\"wp-image-1461\" srcset=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2022\/05\/image-1024x492.png 1024w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2022\/05\/image-300x144.png 300w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2022\/05\/image-768x369.png 768w, https:\/\/markjohntaylor.com\/blog\/wordpress\/wp-content\/uploads\/2022\/05\/image.png 1320w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n","protected":false},"excerpt":{"rendered":"<p>The basic idea is open addressing, but without any redirections (thus making Swiss tables very memory efficient). Also, Swiss tables store a densely packed array of metadata with each entry consisting of 1 byte (which makes the metadata table easier to fit into the CPU cache, as opposed to, say, metadata of pointers of 8 &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/2022\/05\/08\/awesome-swiss-tables\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Awesome Swiss Tables&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[15],"tags":[],"_links":{"self":[{"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/posts\/1456"}],"collection":[{"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/comments?post=1456"}],"version-history":[{"count":12,"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/posts\/1456\/revisions"}],"predecessor-version":[{"id":1769,"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/posts\/1456\/revisions\/1769"}],"wp:attachment":[{"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/media?parent=1456"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/categories?post=1456"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/markjohntaylor.com\/blog\/wordpress\/index.php\/wp-json\/wp\/v2\/tags?post=1456"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}