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?

Fast Branchless Quicksort Using Sorting-Networks with C and C++ Interface

Proposta TLBIC v4.1 (PT-BR): construída com IA, para chegar a quem mais precisa

Why Only Cars Have ADAS Not Tow Wheelers?

MCP-Gateway

Be Delusional

Floating-Point Error Handling in C++: What Works

Optimizing for Text-Mode Browsers

A wiki in a single file? A look at Feather Wiki

Revo, the Programming Language

RenderLab – Prototype rendering techniques and renderers in the browser

SpaceX IPO to Be Largest Ever at $135 Share Price

The SpaceX IPO Will Be the Theft of the Century

The Industrialization of Academic Research

1979: Will Word Processors start a home working revolution?

Fired 60 Minutes Scott Pelley: CBS told to inject 'falsehoods' into reporting

Uber slashes people division by nearly 25%; CEO says 'changes are necessary'

Microsoft EXecution Container (MXC)

Bitcoin Falls to Pre-Iran Conflict Low as Crypto Slide Extends

Show HN: Realistic procedural fire effect via naive algorithm

SpaceX targets biggest ever stock market debut

OpenAI CEO Sam Altman makes a lot of predictions. Here's how they fared so far

The Hardest Fork

Onion: "Google Opt Out Lets Users Protect Privacy by Moving to Remote Village" [video]

Ongoing NPM supply chain attack uses binding.gyp to spread like a worm

License plate frame pattern optimizer for evading ALPR

Ask HN: Google's AI mode not available on Firefox?

GitHub Copilot's metered billing: the wake-up call we needed (but didn't want)

Will OSS that does not use AI disappear?

Reverse engineered Tesla's new dashcam encryption

Zeugma and Syllepsis