git.iko.soy/urbit.org
on 625febc help sign in
urbit.org/content/grants/loom-pointer-compression.md
62 lines 2.9 kB history raw
1+++
2title = "Loom Pointer Compression"
3date = "2022-08-11"
5[taxonomies]
6grant_type = [ "Apprenticeship" ]
7grant_category = [ "Core Dev", "Runtime" ]
9[extra]
10image = ""
11description = "Expand the maximum addressable loom size"
12reward = "1 star"
13mentor = ["~fanfun-mocbud"]
14assignee = ["~barter-simsum"]
15grant_id = "A0173"
16completed = false
17canceled = false
18work_request_link = "https://airtable.com/shr4qt9t9kz7RaOIa?prefill_Grant+ID=A0173&prefill_Grant+Name=Loom%20Pointer%20Compression"
19+++
21# Loom Pointer Compression Apprenticeship
23This project makes it possible to at least double the maximum addressable loom space, which is constrained by the number of bits in a loom offset (`u3_post`).
25U3 uses 32-bit noun references, and 2 of those bits are used for type tags (in the case of indirect references to loom allocations). The remaining bits are availabe for use as word-aligned (4-byte) offsets/indexes into the memory of the loom, and all allocations are sized and aligned in terms of words.
27Increasing the alignment boundaries of loom allocations to some larger power-of-two (call it `X`) lets us effectively use additional bits (`log2(X)` to be precise) in our loom offsets -- since those bits will always be zero, we can shift them off and don't need to store them inside our 32-bit references. Each additional bit doubles the size of the addressable space; in this way, we can grow the loom without switching from 32-bit to 64-bit references (which should also be done, but is a larger project subject to other constraints). This "pointer compression" trick is used to great effect by the JVM.
29Switching to 8-byte (2-word) alignment buys us one additional bit, and since our minimum allocation (the size of a cell) is 6 words, it does so without imposing costly padding. Higher levels of alignment should be considered, but may not be worthwhile outside of specialized use-cases, as they will involve padding of all cell allocations (barring more dramatic changes to the memory layout of nouns).
31## Deliverables
33- an updated allocator (`u3a_walloc()` and friends) that ensures at least 8-byte (2-word) alignment for all loom allocations
34- an updated de/reference api that compresses pointer-to-offset (`u3a_outa()`) and decompresses offset-to-pointer (`u3a_into()`)
35- a migration from the old to new heap layout (`u3m_pack()`, but capable of reordering the heap to adjust minimum allocation alignment)
37## User Stories
39- moar nouns
41## Prequisites
43- proficiency in C
44- familiarity with custom allocators, bit-twiddling, &c
46## Educational Outcomes for the Apprentice
48The apprentice will learn about:
50- vere/u3
51- the loom and road system
52- our allocator
54## Responsibilities of the Mentor
56- technical direction
57- code review
58- release plan
60## Duration and Compensation
62Expected duration is two months. Compensation is 1 star upon successful completion of the apprenticeship.