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?

India's 'Cockroach' Protesters Declare Rare Victory over Government

We built the new fastest API for GLM-5.2

Show HN: Raise a virtual pet with your friend/partner

Google ignored my site for 13 weeks, so I audited everyone who outranks me

An ESP32 based plane radar for my desk

Lessons from Building My Own Products as a Freelance Engineer

Four Proposals to Improve Fuel Economy Standards (2021)

Show HN: Rules that stop AI coding agents from breaking working code

Show HN: I enhanced the UX for TemplatesOn, what do you think?

Multiple LLMs trying to reach a consensus

Show HN: I mapped every US golf course – 18k courses, free, no signup

What Colorado consumers should know about the cyclospora outbreak

Ajay Kumar on running MCP in production [audio]

When You Build the Wrong Thing

Show HN: What 180k words look like as a temporal knowledge graph (Oz series)

Do People Swallow 8 Spiders a Year While They Sleep? (2014)

How Many Bits Can an Adapter Write? Capacity and Memorization of LoRA

Dartmouth Workshop on Artificial Intelligence (1956)

1209X Agentic Engineering

Sally the Robot Was Coming to a New York School. Then the Plug Was Pulled

Show HN: Fitter – declarative web-data extraction,running in the browser also

NYU Stern pricing expert: The hidden 'AI tax' hitting your next phone

Show HN: ZWPlayer – Free player with interactive annotations and subtitle search

Scottish tax hike for high earners backfires with loss of £22M

The hidden cost of AI: Why your town is negotiating with Amazon and Microsoft

An automated website audit tool using Gemini and n8n

Alien World Chemistry Found Inside Meteorite That Struck New Jersey Home

Space Oddity; Review of Slobodian and Tarnoff's "Muskism"

AI Can Now Design Drugs in Seconds; We Still Can't Tell You If They Work

Forer Effect