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?

PRINTABLE.MD

The Five Stages of Being Replaced by Your Autocomplete

PIZD, a Rust compressor exploring structural deduplication

How to Start a Defence Tech Startup in the UK: Part 1

A React component for building Web forms from JSON Schema

Show HN: Continue Your Google AI Mode Chats in Gemini/Claude

Probably NOT use the Linux eBPF/Rust XDR I built alone

Nvidia Eyes Software Revenue with a $2k per GPU Yearly Figure from Huang

RTX 4000 Pro Blackwell SFF performance hacks

A tiny app for C# dotnet design Window Form

Thiel's leaked lectures on the end of the world

Show HN: pw-repl – A Playwright-powered REPL for you and your agents to share

Notes on loneliness (Tommy Dixon)

I translated North Korean pop into American [video]

HackDigest: Daily three-sentence news summaries in Korean or English

China's tech giants are paying 1M yuan for a new kind of AI engineer

Peter Thiel says Apple has done 'nothing new' after Steve Jobs

MustardOS is custom firmware (CFW) for handheld gaming devices

PyMagic a tiny DSL to write models/specs in Python

Slavoj ŽIžek: Only Desperation Can Save Us from Ecology, AI, and War [video]

Blackwell Brings NUMA Back, Inside One GPU

Show HN: Hazzel – A terminal coding harness that stays small on purpose

Show HN: Tabverse – a free, open-source, with self-hostable server Workona clone

Ask HN: Did crates.io stop processing new crate publishes?

Aw1-breaker – Sub-millisecond AST circuit breaker for AI agent tool calls

Data-Oriented Design in Yuku's Parser

Raspberry Pi Pico W Irrigation – Telegram and Google Calendar All on Pico

Rosettes and Other Hidden Traces of Hamburg's Tram

A cool 3D interactive demo of neuroevolution with supermario

Science could lift Italy's sinking cities back up