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?

Devon

LinkLens: Protect Yourself from Clickbait

After banning foreign routers, FCC says existing ones can get updates until 2029

Chinese Powev Enters DDR5 Market with Up to 64 GB Udimm, Sodimm, and Rdimm

A Caddy Cert Expired Because Systemd-Resolved Was Selectively Broken

Closure of Radio 4 on Long Wave (LW)

A brain reward circuit inhibited by next-generation weight-loss drugs in mice

I Disagree with Paul Graham

Show HN: Route optimization API that solves fleet planning as a single problem

PostHog Code

When readers would rather listen

An Ice Cold Take on CI Config Systems

K-12's biggest failure is making us think learning ends

Red flags when building AI

AI is a Sword not a Shield [video]

Typing Some Python Quirks

A million baby monitors and security cameras were easily viewable by hackers

Ask HN: How are you preparing for interviews nowadays?

Show HN: Compiled an archive of copium content for SF Bay Area engineers

Uniform Rental Contracts Explain the U.S. Economy

What Challenging a Bowling Monopoly Says About America

Counterfactual samples synthesizing for mitigating hallucination in LLMs

Tashk – a todo manager written in pure bash

The lab where Ford is trying to crack the code on cheap EVs

Elon Musk and Tim Cook among CEOs expected to accompany Trump on China trip

Tensor Shapes

French woman was told by doctors hantavirus symptoms were just anxiety

OpenDyslexic: A Typeface for Dyslexia

Cloud Storage Rapid: Turbocharged object storage for AI and analytics

My First AI Project: An "Evidence-Based" System Architect. Looking for Feedback