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?

Fireshow: Don't send the deck later – walk them through it live on the call

The Mathematical Dance Inside Plant Cells

What Makes Art Great?

What Happened with Mars Sample Return?

Barocal can cool your food and drink by squeezing a hunk of plastic crystals

For Google Advertisers Who Overpaid the Monopoly – Don't Hate, Arbitrate

GitHub Is Down

Is Mercury.com Down?

An Update on ERSC Availability

KAL – The Kube API Linter

Evolution has reused the same genes for 120M years

Sierra Raises $950M at $15B Valuation

Unified physics theory machine-verified in Lean 4 (504 K lines, 0 sorry)

Postgresparser: ANTLR-based PostgreSQL query parser for Go

BrowseNotes – Sticky notes anchored to text on any webpage

The AI supply crunch is here

Amazon Supply Chain Services: Amazon’s logistics network, open to every business

Quantifying the impact of AI data centers in a warming world

Expanded AMD HDMI 2.1 support is coming to Linux

Alberta voter list leak is a potential public safety disaster

Show HN: Bonsai 1.7B ternary model at 442T/s on M4 Max

Ask HN: What is your favorite YouTube channel for developers?

Content for Content's Sake

Representation Is All You Need

"Open" doesn't mean what it used to

Seed oils in the pathogenesis of CVD also warrants further investigation

Hedera Introduces CLPR: The Bridgeless Cross-Ledger Protocol

Hello, Babashka

Ask HN: A Spec Driven Back end development platform to build and evolve safely

Meta's historic loss in court could cost more than $375M