From 9d45f3befbc929f6555745127b2a4de073229755 Mon Sep 17 00:00:00 2001 From: Taylan Kammer Date: Wed, 26 Aug 2026 22:14:37 +0200 Subject: Another note update. --- notes/260826-use-alloc.md | 12 ++++++++++-- 1 file changed, 10 insertions(+), 2 deletions(-) (limited to 'notes/260826-use-alloc.md') diff --git a/notes/260826-use-alloc.md b/notes/260826-use-alloc.md index 394b69d..0fc2b29 100644 --- a/notes/260826-use-alloc.md +++ b/notes/260826-use-alloc.md @@ -123,9 +123,17 @@ a 1024-byte block. Blocks of size 2 to 16 KiB need tracking in units of 16 bytes, so that's from 128 bits for a 2 KiB block to 1024 bits for a 16 KiB block. Repeat the math for the larger alignments. -Allocating a new slot should of course not require scanning possible +*Update:* No, that's nonsense. For example, a 1024-byte Block cannot +have objects smaller than 33 bytes (which would be put into the next +smaller Block type) and it pads to multiples of 8, so the smallest +allocation would be 40 bytes; thus we only need 1024 / 40 = 25 bits?? +Wow, that seems really good. Am I messing up some part of the maths? +I think it's correct, and it seems that the bit-count always stays +under 32 bits, so we can just uniformly use 32-bit integers. + +Allocating a new slot should of course not require scanning possibly huge numbers of bitmaps from start to end. We keep track of the last -acquired Block and try to fit the next allocation, acquiring a new +acquired Block, and try to fit the next allocation, acquiring a new Block if it doesn't fit. Given that objects can only occupy up to 1/16 of a Block, this means we waste at most that about that much space at the end of a Block due to the next object not fitting. -- cgit v1.2.3