>regions (e.g., maybe only one page?) than the rather simple
>linked-list code in NetBSD.

if it is the linked list, then it should be easy enough to tell by
breaking to ddb when it gets slow, doing a "ps/m" (old vm) or
"ps/a" (uvm), getting the vmspace/map kernel address of the X
process and doing a "show map" on that address.   the number 
of entires shows how long that linked list is.   uvm still has 
the linked list (with the one item cache). 

e.g.:

login: ~Stopped at      _Debugger+0x4:  leave
db> ps/a
 PID          COMMAND      STRUCT PROC *            UAREA *     VMSPACE/VM_MAP
 ...
249        XF86_SVGA         0xf0565200         0xf2f0e000         0xf0569d00
 ...
db> show map 0xf0569d00
MAP 0xf0569d00: [0x0->0xeffbf000]
        pmap=0xf0567800, #ent=41, sz=45834240, ref=1, main=T, version=1115
db> c

so my X server has 41 entrys.

chuck