{"id":2031,"date":"2016-02-13T16:00:17","date_gmt":"2016-02-13T16:00:17","guid":{"rendered":"https:\/\/www.reenigne.org\/blog\/?p=2031"},"modified":"2016-02-11T09:52:48","modified_gmt":"2016-02-11T09:52:48","slug":"2-forward-1-back-list-for-ravioli","status":"publish","type":"post","link":"https:\/\/www.reenigne.org\/blog\/2-forward-1-back-list-for-ravioli\/","title":{"rendered":"2-forward, 1-back list for ravioli"},"content":{"rendered":"

It turns out that having three “low-level” pointers per “high-level” pointer is not actually necessary in ravioli memory<\/a> – two is enough.<\/p>\n

The reason for this is that all the entries in the linked list are actually the same, so we don’t need to store the pointer value in every element of the list. What we can instead do is to have two types of node:<\/p>\n

    \n
  1. A node containing the pointer to the target and a pointer to the next node in the linked list.<\/li>\n
  2. A node containing a pointer to the next node in the linked list and a pointer that points back in the linked list either 2 or 3 entries.<\/li>\n<\/ol>\n

    To find the target pointer if you have a node that doesn’t contain it, just advance through the linked list until you do. To add a pointer to the linked list, add a forward pointer if that would cause the next backward pointer to point back 3 entries, otherwise add new backwards pointer so there are two “back 2” entries and the invariants are maintained. To remove a pointer, do the opposite to adding it.<\/p>\n

    If we want to make each raviolo a power of 2 bytes in size, we can then have 3 “high-level” pointers per raviolo (it doesn’t allow us to make the ravioli smaller, since we still need a pointer for the vtable and to the first entry in that node’s reference list).<\/p>\n

    However, I’ve since moved on to a more conceptually clean version of ravioli, which I’ll talk about tomorrow.<\/p>\n","protected":false},"excerpt":{"rendered":"

    It turns out that having three “low-level” pointers per “high-level” pointer is not actually necessary in ravioli memory – two is enough. The reason for this is that all the entries in the linked list are actually the same, so we don’t need to store the pointer value in every element of the list. What […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[39,4,27],"tags":[],"class_list":["post-2031","post","type-post","status-publish","format-standard","hentry","category-algorithms","category-computer","category-language"],"_links":{"self":[{"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/posts\/2031","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/comments?post=2031"}],"version-history":[{"count":2,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/posts\/2031\/revisions"}],"predecessor-version":[{"id":2033,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/posts\/2031\/revisions\/2033"}],"wp:attachment":[{"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/media?parent=2031"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/categories?post=2031"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/tags?post=2031"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}