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?

U.S. Supreme Court to review 1868 federal ban on home distilling of liquor

A Forgotten 1980 Reversible Computer, and the AI That Just Cut Quantum Costs 17x

Privacy Badger for Safari on macOS

Show HN: Rouler – Steer Windows traffic per app or IP across multiple interfaces

AWS CFO joked about the financial toll of AI. An internal recording reveals why

The AfD leak site's emails shows nazism from party members

Pixel: Build Graphical Applications in the Terminal

Should agent-memory benchmarks test stale information?

Show HN: An Open Source Aircraft

Refuseless: Open and Abliterated LLMs

Show HN: Don't Get Nerf'd by Document Processing

Show HN: AML CYCLE 2, a benchmark for long-term agent memory

Show HN: SendReward – gift cards at face value, dashboard or one API call

Cloudflare: There is a major outage on Zero Trust services

Clockwork Mechanics, Maintenance, and Metaphors in the Late Middle Ages

Exa 3.0

Voice packs plus an open-source agent for texts, calls and Slack

Cash every week iPhone app: way to see where your money goes, one week at a time

Alberta referendum: Province awaits results after delays on voting day

Textideo Director – an AI video creation tool for scenes, shots

How to read QR codes by hand (and make bad ones that work) [video]

Don't Choose. Join

Healthy Reef Sounds Can Boost Coral and Fish Recovery Efforts

Edward Snowden on Palestine and Sam Altman [video]

Go will reject certificate chains containing eight distrusted SPKIs

CNN's Christiane Amanpour to depart network after 43 years

Show HN: Search for AI-agents and usefulness score

Supercapacitor cement is key to buildings that store their own power

LinSparkle: A sparkle style auto updated for AppImages

Scaling to Test-Time Iterations with Loop-Native Attention