[oscardssmith]

By moving the storage from Vector to Memory (on 1.11+) we can save a couple pointer indirections (and a little bit of struct size). We also speed up ht_keyindex by splitting the direct parameter into 2 separate functions which removes the if/else from the probing loop. We also remove the maxprobe parameter which just seems worse for performance. The benchmarks show that this version is consistently faster for insertions, and slightly faster for lookup of existing keys.

  using BenchmarkTools, OrderedCollections, Printf
  build(n)=(d=OrderedDict{Int,Int}(); for i in 1:n; d[i]=i; end; d)
  hit(d,ks)=(s=0; @inbounds for k in ks; s+=d[k]; end; s)
  miss(d,ks)=(s=0; @inbounds for k in ks; s+=get(d,k,0); end; s)
  upd(d,ks)=(@inbounds for k in ks; d[k]=k+1; end)
  itr(d)=(s=0; for (k,v) in d; s+=k; s+=v; end; s)
  m(b)=minimum(b).time
  println("size      hit     miss   insert   update     iter   (ns/op)")
  for n in (8, 64, 1000, 100_000)
      d=build(n); ks=collect(1:n); mk=collect(n+1:2n)
      @printf("%7d %7.2f %7.2f %8.2f %8.2f %8.2f\n", n,
          m(@benchmark hit($d,$ks) seconds=0.4)/n,
          m(@benchmark miss($d,$mk) seconds=0.4)/n,
          m(@benchmark build($n) seconds=0.4)/n,
          m(@benchmark upd($d,$ks) seconds=0.4)/n,
          m(@benchmark itr($d) seconds=0.4)/n)
  end
  

size	op	master	PR	Δ
8	hit	2.70	2.67	~flat
8	insert	17.07	8.35	−51%
8	update	4.35	4.06	−7%
64	hit	2.53	2.37	−6%
64	insert	14.50	10.61	−27%
64	update	4.12	3.87	−6%
1000	hit	2.59	2.36	−9%
1000	insert	11.70	7.60	−35%
1000	update	4.57	4.30	−6%
100000	hit	7.84	7.52	−4%
100000	insert	21.71	16.28	−25%
100000	update	10.92	10.29	−6%

Coauthored by claude (but carefully reviewed)

[KristofferC]

Allocating this here doesn't look great. Ref #169 for a probably better solution.

[oscardssmith]

seems reasonable. Will rebase once that merges.

[KristofferC]

According to the robot this has bugs so should not be merged.

---

1. [P1] popfirst! accesses invalid memory on an empty dictionary. After d = OrderedDict(1 => 10); empty!(d); popfirst!(d), the retained buffer allows h.keys[1] to succeed. Lookup returns -1, which reaches unchecked accesses in _pop! and _delete!. My reproduction returned a garbage value; the base commit throws BoundsError. Check emptiness before reading the key. [Lines 397–401](

   OrderedCollections.jl/src/ordered_dict.jl

   Lines 397 to 401 in e14702c

   	function popfirst!(h::OrderedDict)
   	h.ndel > 0 && rehash!(h)
   	key = h.keys[1]
   	index = ht_slotindex(h, key)
   	key => _pop!(h, index)

   )

2. [P1] Removing the finalizer checks corrupts dictionaries during rehashing. If a finalizer deletes an entry while hash(k) runs, rehashing publishes stale entries without retrying. I reproduced a deleted key reappearing, with length(d) == 2 but three entries yielded by iteration. Collecting that result crashed Julia. The same reproduction works correctly on the base commit. Restore deletion detection and retry in both rehash branches. [Lines 171–180](

   OrderedCollections.jl/src/ordered_dict.jl

   Lines 171 to 180 in e14702c

   	@inbounds copyto!(newkeys, 1, oldk, 1, oldlen)
   	@inbounds copyto!(newvals, 1, oldv, 1, oldlen)
   	@inbounds for i = 1:oldlen
   	k = newkeys[i]
   	index = hashindex(k, newsz)
   	while slots[index] != 0
   	index = (index & (newsz-1)) + 1
   	end
   	slots[index] = i
   	end

   )

3. [P2] empty! retains all key and value references. Resetting len leaves objects reachable through the backing buffers. A WeakRef test confirmed both key and value survive full GC after empty!; both are collected on the base commit. Clear reference-bearing entries or replace the buffers. This also affects OrderedSet. [Lines 203–208](

   OrderedCollections.jl/src/ordered_dict.jl

   Lines 203 to 208 in e14702c

   	function empty!(h::OrderedDict{K,V}) where {K,V}
   	fill!(h.slots, 0)
   	h.len = 0
   	h.ndel = 0
   	h.dirty = true
   	return h

   )

Existing OrderedDict and OrderedSet tests pass on Julia 1.12.7 and 1.10.12, with one expected broken test on 1.10. The targeted reproductions expose gaps in that coverage.