Post #1420914

2026-04-19 21:17 UTC

CDR-coding might be practical on modern architectures after all. for example, on x86, put these CDR bits at the top of a word: 00 EOL cdr of this cell is NIL 01 NEXT cdr of this cell is next cell 10 ATOM this is not a list cell 11 GONE this cell has moved elsewhere and use the following access code fwd mov eax,[eax*4] ; don't let FWDs into regs cmp eax,$C000000 jae fwd ret car mov edx,[eax*4] ; guaranteed not FWD test eax,eax ; so if MSB set, jc rtn ; must be ATOM mov eax,edx cmp edx,$C000000 jae fwd rtn ret cdr mov edx,[eax*4+4] shl eax,1 jns NIL mov eax,edx cmp edx,$C000000 jae fwd ret by and large, the mov will shadow the cost of testing - so that essentially the latter will be free note that there's no code to denote a CONS cell. i'm not sure when i realised that you don't need one - that it's sufficient to have CDR-NEXT and FWD, because you can make a CONS cell out of [ NEXT FWD ], and as long as you always follow FWDs somewhere (a good strategy, which is implemented above, is to never allow them into CPU registers), they're transparent. it might make sense - and save some space - to put $C0000000 into a register - say, ebp - so comparing it takes two bytes instead of 6. especially when open-coding functions (gods, i wish Intel hadn't removed the conditionall calls and returns from the 8080 instruction set...!)

Replies (2)

@millihertz@oldbytes.space 2026-04-21 02:39

turns out that even if you're using an 8080 / Z80, CDR-coding might be worth it. granted, the reduced form of CDR-coding where you only get NEXT and FWD, but again, you can either not allow forwarders into registers, or start by resolving any forwarders in registers. but the forwarder resolver is short enough to be stuffed into a rst. sort of: org $1E mov e,m xchg reify mov a,l ; rst 4 rar rnc mov d,m dcr l jmp $1E cadr inr l inx h rst 4 car mov e,m inr l mov d,m jmp $1E cddr inr l inx h rst 4 cdr inr l inx h jmp $20 atom push h ; atom if car X=X call car xchg pop d mov a,l xra e mov e,a mov a,h xra d or e jnz untrue lxi h,TRUE ret untrue lxi h,FALSE ret it turns out that resolving forwarders before allowing them into registers is quicker. specifically, 21 cycles quicker on a Z80: the difference between JMP x and RST x / RET ... RET. CONS is almost certainly something you want in a register too. this form of CDR-coding doesn't save us from having to terminate lists with NIL - quite a big deal when the average length of a Lisp list is 4 items! and possibly the wrong optimisation when only 1% of CDRs don't point at the next memory address after linearisation. but a signficant limitation of using a a scheme where a set bit means END rather than FWD is that it becomes impossible to represent a zero-length list (without a hack), or to represent the 1% of CONSes whose CDRs don't point to the next cell in memory (without a different hack).

Open ##1493692
@SpindleyQ@gamemaking.social 2026-04-21 02:51

@millihertz wrapping my head around this... should the `JC rtn` in `car` be a JNGE? CF is always 0 after a TEST, you want to check SF, right?

Open ##1493694