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?

Leap seconds face judgment day as time lords prepare to vote

Lix 2.96 "Bingsu"

Georgia man sues Flock, sheriff's office over alleged ALPR-fueled retaliation

Ukraine Starlink Access Restricted as Musk Says Zelensky 'Has Gone Too Far'

OpenAI bugging suspect booked one-way ticket to Saudi Arabia

Public Risk Monitor

Schools across US protest FCC plan that could disconnect kids from Internet

Vintage Cassettes: 1963-2010

Liquid clustering isn't free, it's just cheaper to get wrong

TX real estate investor gets 15 yrs federal prison for investment fraud scheme

Show HN: Are interstellar visitors alien probes?

Brand is who you are

A Reporter Returns to China to Find It Richer, but Also Highly Paranoid

Hell's Committee: Vibe coded party game

Show HN: Digs - For Passionate Music Explorers (like Goodreads for music)

What models accelerate and where expertise still matters

Scientists make contact with an uncontrolled agent swarm

Anthropic's Scion is heavily inspired by Mononoke

Yandex outage: data shows that instead of going dark, malicious bots moved

OpenAI Cuts Codex Desktop Storage Use by 60 Percent

Play Diablo II: Resurrected in 3D

Sceptive: //Bl0ck – Preemptive Cyberdefense Grid

The AI labor apocalypse is on hold (for now)

OpenAI's blockbuster math proof isn't what you think it is

We're Learning to Live with Waymos. It's Going Weird

Berkshire Hathaway Builds 4% Stake in Bending Spoons

DataAnalyticsBench

Making 3D Model with Meta Oakley AI Glasses and Digital Tape Measure [video]

M-Vave FM-1 Resource Hub

Leverage Maxxing