Packed Data Support in Haskell

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

77•matt_d•10mo ago

Comments

nine_k•10mo 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•10mo ago

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

Zolomon•10mo ago

They mention this in the article.

spockz•10mo ago

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

cstrahan•10mo ago

No, one example of why being variable sized integers.

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

carterschonwald•10mo ago

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

tlb•10mo 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•10mo 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•10mo 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•10mo ago

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

lordleft•10mo ago

This was very well written. Excellent article!

NetOpWibby•10mo ago

Is this like MessagePack for Haskell?

Synaps a self-hosted personal health monitor as a weighted knowledge grap

Steve Jobs, speech at the Apple campus (1999) [video]

Can It Resolve Doom? Game Engine in 2k DNS Records

Yann LeCun's LeWorldModel: Stable End-to-End JEPA from Pixels

America's Chief Financial Officers Say AI Is Coming for Admin Jobs

The Wrong Abstraction

A Mysterious Numbers Station Is Broadcasting Through the Iran War

OpenBSD.Amsterdam

The orderbook dynamics of prediction markets

Donut Lab's solid-state battery could barely hold a charge after getting damaged

Show HN: Offline-first UK train planner

curl > /dev/sda: How I made a Linux distro that runs wget | dd

More Magic Math from OpenAI?

Asyncio is neither fast nor slow

Emerging SaaS trends that are accelerating

Show HN: CertPulse – Certificate monitoring for multi-cloud teams

Show HN: The complete Open Library catalog in clean, analysis-ready Parquet

Make better decisions based on criteria that are important to you

Are Strings Still Our Best Hope for a Theory of Everything?

SIDN chooses European-based infrastructure for .nl DNS anycast (i3D.net)

Important Updates to GitHub Copilot for Students

The ancient reason there are 60 minutes in an hour

I built a 30-second dinner decider because weeknight decision fatigue is real

ISS: Instant Space Switcher for macOS

Head-mounted VR hardware will never happen, says Neal Stephenson

Arm to host 'Arm Everywhere' event and webcast

Show HN: Using the Web Audio API to simulate various tuning forks

Local Bernstein theory, and lower bounds for Lebesgue constants

Microsoft's "Fix" for Windows 11: Flowers After the Beating

Users Quit ChatGPT for Claude in 1,487% Surge