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?

George Lucas says rejecting AI is like rejecting cars in favour of horses

Texas Police Spent $4.5M on Four Chevy Tahoes

AI or Not

How India spends - a running account of the Indian economy

A tiny 2504 byte Windows snipping tool written in 32-bit MASM assembly:D

Making Software – How to make a font

AI models' values are different from most people's

Show HN: Sogni Unlimited – flat-rate unlimited image/video on decentralized GPUs

Marco Rubio launches campaign to dismantle international criminal court

We Stopped Using SDKs

I Talk to My Deceased Grandparents Every Day Using This AI App

1X's NEO hand is genuinely impressive. The economics are brutal

Looking for developers with high-token AI workflows

LinkedIn is a cesspool of scammers and identity theft

Helsing's 'crazy' valuation raises defence tech bubble concerns

Show HN: Workaround – review and clean up your GitHub stars

The Math Behind "AI Will Take Your Job" Is Laughably Wrong [video]

Lobste.rs is now running on SQLite

Meta used AI to tag workers who took leave to be laid off, lawsuit claims

You can write in LLMese, but you don't have to

Job Hunters Are Using AI to Cheat in Interviews, and Failing at the Office

Electron isAccessibilitySupportEnabled broken when running JAWS since v34

How Brands Sneak in Cheaper Ingredients to Protect Their Profit Margins

Show HN: I turned lender underwriting criteria into a 7-question quiz

Telstra outage blamed on known bug in obsolete server

We don't let the LLM decide what's clinically allowed

Trust but Verify? Uncovering the Security Debt of Autonomous Coding Agents

Xtree Fan Page

Google and Epic stop fighting – third-party Android app stores coming next week

Show HN: I open-sourced the portal I built for a client's vibe-coded apps