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?

Air Conditioning Is Almost Universal in the US and Japan – But Not Elsewhere

War is not god, neither is AI

Why Some People Are Born with Devastating Gene Mutations–and Never Get Sick

Google Buys Spirit Airlines' Emails, Files and Flight Records for $10M

One Night in Uzbekistan

And the universe said you are the universe

Mice learn to think out of the box

Migrate Repo to TypeScript 7

A limit order book and matching engine in Go

What Happened: OpenAI and HuggingFace

When Postgres Isn't the Process That Kills Your Database

I'm Sick of Reading AI-Written Posts

Tumble Forth – from assembly to OS with C compiler

Death to the Self-Playing Game

Does every question mark deserve a Betteridge?

Multiple sequence alignment using WebGPU

Show HN: CSVtoTable – turn a CSV/XLSX into one self-contained HTML file

Shenzhen Night Walk [video]

Robotics Software

Windmill.dev is not "fully open-sourced (AGPLv3)"

Brazilian Rank Links

Mersenne Twister in a 15-Year-Old Game Binary

Bringing the cybersecurity capabilities of Claude Mythos 5 to more defenders

Britain would be bonkers to ditch Palantir

Printing Lists

AI is about to uncover a hidden world of animal communication

His Wedding Guests Were Arriving–Just as His $45B Fund Was Falling Apart

The Meta Chalkboard

Sharding pytest by file cut collection time from 3 minutes to 40 seconds

Postgres SELECT DISTINCT does not scale