[ANN] StaticDictTrees.jl: Fast dictionary trees with zero-allocation views

Package Announcements
1

Hi everyone! :waving_hand:

I’d like to announce the StaticDictTrees.jl package. It provides a high-performance dictionary with Tuples as keys, and with the added functionality of providing views into any data subset identified by an incomplete key.

If you’ve ever used a Dict{Tuple, T} and wished you could instantly isolate all entries sharing a specific prefix without an expensive O(N) filter, this package is for you.

An example is worth a million words:

using StaticDictTrees

#  Create a static dict tree
metrics = SDTree((:prod, :web, :cpu) => 42.5,
                 (:prod, :web, :ram) => 78.1,
                 (:prod, :db,  :cpu) => 12.0,
                 (:stage, :web, :cpu) => 8.4)

# Standard full-key lookup
metrics[:prod, :web, :cpu] # 42.5

# Take a zero-allocation, type-stable view of a sub-branch
prod_web = view(metrics, (:prod, :web))

# The view behaves exactly like a relative AbstractDict ...
prod_web[:ram] # 78.1

# ... and any modification in a view is reflected in the original tree
prod_web[:ram] = 99.
metrics[:prod, :web, :ram] # 99.

Comments are welcome!

2

Your (Gemini’s?) design for item deletion sucks. Two approaches that make sense:

  1. Refuse to support deletion.
  2. Don’t delete the items from the arrays which necessitates the terrible “shift index by one”; instead Base._unsetindex! the slot. On deletion, check whether there are too many currently empty array slots, and if so, reassign all of them at once. This turns deletion from always O(N) into amortized O(1), worst-case O(N).

Generally, I find publication / open-sourcing of this kind of AI-sloppy package of questionable value.

Sure, it can fit your need. Better an AI-sloppy solution than no solution, if writing good code is uneconomical for your usecase.

But then: Why publish and advertise it here? Anyone who ever finds themselves in the same position of needing this functionality badly enough to accept slop can generate the same kind of slop themselves. I don’t see anyone having any reason to take your stale gemini-slop over the gemini-slop that a future model can spit out.

All that being said, :+1: for the AI disclosure!

PS. branch_lookup is effectively untyped. This is unforced – in your design, you could give it a real type.