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?

What makes good magnet programs attractive?

Ask HN: How did your boss's behavior change with the rise of AI?

Granola Class Action Lawsuit

WTF Happened in 1971?

Show HN: Wisp – a Linux shell with Lua scripting and structured pipelines

Bloom Filters

AI doesn't generate working products, that's still your job

Amgen Reports Breach to SEC

How Functional Is Human Tetrachromacy? (Ooqui) [video]

Google plans to exempt sanctioned nations from Android developer verification

Show HN: Habit Dungeon – RPG gamification that helps good habits stick

Solid Queue 1.6.0 now supports fiber workers

Silicon Valley loves young founders. Until it doesn't

Situated Software (2004)

Ten advances in mathematics and theoretical computer science

Is AI Conscious? [video]

Ats Resume Checker

The OpenCode default session prompts for plan and edit

Marketing sucks when all you want to do is build."builder's dopamine"

Future euro banknote design proposals

Most speed readers break on Japanese, Chinese and Thai

Show HN: Lightweight, S3-compatible object storage server

Police in US are using the power of podcasts to crack unsolved murders

Churchill's Ersatz Meeting with Lincoln's Ghost (2018)

A migrant surge tests Spain's open policies

Chinese AI Researchers Are Finding Their Voice on X

A big win for Android interoperability

Spain Regains Control of Enclave After Migrants Overrun It

GPT has proved nonsofic groups are exist

OpenAI's work on Git for large repositories