When this was posted to lobsters someone shared this relevant link: https://curiouscoding.nl/posts/static-search-tree/

The bucket boundaries are often chosen from a random sample of the data, if the input data is very large. Sorting is O(nlogn), but using binary search per value to assign a bucket is O(n), plus the cost of creating the buckets on a sample. So once you hit a large enough number of values this scales better.

Binary search does give random access but in this case there's only up to 255 buckets typically, so it's random access on cached memory.

Can you say more about what happens for bucket assignment? Eg is it appending to a file or writing to a 2d array?

Agreed on linear vs n log n, ofc, and streaming considerations might also be relevant

Better guesses reduce the number of guesses, so there will be less branch misprediction, but there will still be mispredictions for each remaining branch. So I would guess branchless interpolation search would still help.

In practice because the real code in scikit-learn is used in parallel, memory bandwidth starts being a problem in real usage. Plus, in the overall algorithm (this is just a small part) the time spent on binary search is now low enough that there are other, more significant bottlenecks elsewhere. So in practice the branchless optimization had enough impact on the original motivating code base that there didn't seem much point spending more time on it.

That's great! Would also be cool (separately from Pydantic use case) to add jiter backend to ijson.

I talk about this more explicitly in the PyCon talk (https://pythonspeed.com/pycon2025/slides/ - video soon) though that's not specifically about Pydantic, but basically:

1. Inefficient parser implementation. It's just... very easy to allocate way too much memory if you don't think about large-scale documents, and very difficult to measure. Common problem with many (but not all) JSON parsers.

2. CPython in-memory representation is large compared to compiled languages. So e.g. 4-digit integer is 5-6 bytes in JSON, 8 in Rust if you do i64, 25ish in CPython. An empty dictionary is 64 bytes.

Funny to see awkward array in this context! (And... do people really store giant datasets in json?!?).

Often the legacy of an engineer (or team) who "did what they had to do" to meet a deadline, and if they wanted to migrate to something better post-launch, weren't allowed to allocate time to go back and do so.

At least JSON or CSV is better than the ad hoc homegrown formats you found at medium-sized companies that came out of the 90's and 00's.

Some people even use AI-generated JSON as a semantic layer over their SQL.

My sweet summer child

Once you switch to ijson it will not save any memory, no, because ijson essentially uses zero memory for the parsing. You're just left with the in-memory representation.

msgspec is much more memory efficient out of the box, yes. Also quite fast.

You can't add extra attributes that weren't part of the original dataclass definition:

  >>> from dataclasses import dataclass
  >>> @dataclass
  ... class C: pass
  ... 
  >>> C().x = 1
  >>> @dataclass(slots=True)
  ... class D: pass
  ... 
  >>> D().x = 1
  Traceback (most recent call last):
    File "<python-input-4>", line 1, in <module>
      D().x = 1
      ^^^^^
  AttributeError: 'D' object has no attribute 'x' and no __dict__ for setting new attributes

Most of the time this is not a thing you actually need to do.

Also some of the introspection stops working e.g. vars().

If you're using dataclasses it's less of an issue because dataclasses.asdict.

I rarely need to dynamically add attributes myself on dataclasses like this but unfortunately this also means things like `@cached_property` won't work because it can't internally cache the method result anywhere.

IIRC you can just include a __dict__ slot and @cached_property should start working again. I

For my PyCon 2025 talk I did this. Video isn't up yet, but slides are here: https://pythonspeed.com/pycon2025/slides/

The linked-from-original-article ijson article was the inspiration for the talk: https://pythonspeed.com/articles/json-memory-streaming/

I have a side question -- what did you use for slides?

One key question in these sort of things is how free() works: it is given a pointer, and it has to decide whether this was sampled or not, with _minimum_ effort.

Poireau does this, IIRC, by putting the pointers it sampled in a different memory address.

Sciagraph (https://sciagraph.com), a profiler I created, uses allocation size. If an allocation is chosen for sampling the profiler makes sure its size is at least 16KiB. Then free() will assume that any allocation 16KiB or larger is sampled. This may not be true, it might be false positive, but it means you don't have to do anything beyond malloc_usable_size() if you have free() on lots and lots of small allocations. A previous iteration used alignment as a heuristic, so that's another option.