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?

Don't Paste the AI, Please

One affiliate now brings in half my SaaS sales

Families with a mutation for gastric cancer have stomachs preemptively removed

FritzHole – FRITZ OS DNS filter blocks unwanted content

Earth Mover's Distance

AI Does Not Change Goodhart or the Folly of Tokenmaxxing

Rewriting a production compiler's IR with AI agents in five weeks

A $21B 'Kids in Chips' Startup Is Scooping Up Nvidia Talent

Prompt Injection in VirusTotal's Code Insights API

Conlang

As Wisconsin cities flee Flock, its shared camera network loses value

KDE's bookmark search ignores Brave because of one unmatched string

Constantine's Bridge Has Surfaced from Beneath the Danube

Democracy vs. the machine: birth of digital age,the warnings that were ignored

Searching for Answers from the Man Accused of Sabotaging Alaska's Senate Race

Wound/wait deadlock-proof mutex design

Suicide hotlines don't seem to help

US LLCs for founders whose country Stripe/Shopify don't support

Who bears the risk in Nvidia's $500B financing platform?

AI Used to Verify Toughest Mathematics Proof Yet

Show HN: Kitsunagu – A platform to find English-speaking professionals in Japan

The most complex time in 20 years to build an enterprise software startup

The hyperscalers' exploding 'purchase commitments' reach $1.5T

Fredkin's Paradox

Handover of In-Context Learning State Across Session Boundaries

We still don't know how people are using AI

Daron Acemoğlu: We Are "At the Cusp of Losing" Liberal Democracy [video]

Show HN: AirStats – Mac menu bar system monitor, 0.046% CPU idle, MIT

The Case for Deep Conversation in a World of Small Talk

Data driven essay: Misogyny kills; misandry kills at scale