Packed Data Support in Haskell

https://arthi-chaud.github.io/posts/packed/

77•matt_d•1y ago

Comments

nine_k•1y ago

> Introducing the ‘packed’ data format, a binary format that allows using data as it is, without the need for a deserialisation step. A notable perk of this format is that traversals on packed trees is proven to be faster than on ‘unpacked’ trees: as the fields of data structures are inlines, there are no pointer jumps, thus making the most of the L1 cache.

That is, a "memory dump -> zero-copy memory read" of a subgraph of Haskell objects, allowing to pass such trees / subgraphs directly over a network. Slightly reminiscent of Cap'n Proto.

90s_dev•1y ago

We are always reinventing wheels. If we didn't, they'd all still be made of wood.

Zolomon•1y ago

They mention this in the article.

spockz•1y ago

It reminds me more of flat buffers though. Does protobuf also have zero allocation (beyond initial ingestion) and no pointer jumps?

cstrahan•1y ago

No, one example of why being variable sized integers.

See https://protobuf.dev/programming-guides/encoding/

carterschonwald•1y ago

One thing that sometimes gets tricky in these things is handling Sub term sharing. I wonder how they implemented it.

tlb•1y ago

> the serialised version of the data is usually bigger than its in-memory representation

I don’t think this is common. Perhaps for arrays of floats serialized as JSON or something. But I can’t think of a case where binary serialization is bigger. Data types like maps are necessarily larger in memory to support fast lookup and mutability.

nine_k•1y ago

I suppose all self-describing formats, like protobuf, or thrift or, well, JSON are bigger than the efficient machine representation, because they carry the schema in every message, one way or another.

IsTom•1y ago

If you use a lot of sharing in immutable data it can grow a lot when serializing. A simple pathological example would be a tree that has all left subtrees same as the right ones. It takes O(height) space in memory, but O(2^height) when serialized.

gitroom•1y ago

honestly i wish more stuff worked this way - fewer hops in memory always makes me happy

lordleft•1y ago

This was very well written. Excellent article!

NetOpWibby•1y ago

Is this like MessagePack for Haskell?

Show HN: VerusCite, a tool to check for hallucinations in academic articles

Reuniting important documents in English theatre history first time in 200 years

If experience is the goal, then you always win

I Made Tinnitus My Friend (Then It Disappeared)

Anti-AI Populism Is Reshaping American Politics

Microsoft confirms it accidentally installed new OneDrive app on Windows 11 PCs

How Tippi Hedren made Vietnamese refugees into nail salon magnates

Tesla Driver Tries 'I Wasn't Driving' Excuse to Get Out of Speeding Ticket

Agentic Constellations: Cartography of the Hidden

Google doesn't need the LLM crown

Windows 11's Weather app uses ~1GB RAM

Transmission has been forked as "ReTransmission"

Show HN: Helicopter Charter and Rentals

As AI guzzles water and energy, we are facing a choice: datacentres or homes?

Apple lied under oath to a federal court. The decision to lie came from Tim Cook

Visor – a QR code that's also a live pay-per-call API

What My Tattoo Artist Taught Me About Life After 50

Rabies in Cape fur seals highlights an unprecedented shift in rabies ecology

Running models on RISC-V with IREE

A Critical Approach of ChatGPT's Impact on Everyday Life

Optimal NYC Neighborhood Locator

FlowG: Turning Your Logs into Metrics

Show HN: Play Tetris in the terminal (solo and pvp)

New x86 CPUID Entry For "EVOLUTIONARY"

Hypotheses

Interviews with key Python developers from the first 25 years

Devs to Anthropic, OpenAI, Cursor, and friends Make security and privacy default

Show HN: Rollcall – Simulated Film Development on iPhone with Shared Rolls

Show HN: AURcade – A tiny self-hosted Git service using cgit and SSH

Keeping Master Green at Scale