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?

Show HN: Relinos – A Hacker's Web Browser – Any Site to API (Open-Source)

Cyberattack hits French blood bank freezer – thwarted by failsafes

We made the first 1 PFLOP/s FlashAttention on a single H100 GPU

Claude Code token cost explorer

Old Vintage Computing Research

Show HN: Pentimento – status and lineage for your coding agent's plan files

Show HN: Usul – Express neural networks as raw math in C++23

Why Morningstar Thinks Anthropic Is Worth $1.7T

Don't Lie to Us, Finland: The Happiness Report Has a Problem

$3B to 0: Blur, once the top NFT marketplace, is shutting down. I designed it

Show HN: Turnus – find cron, launchd and systemd jobs that won't run, and why

Woodpecker

UniXNU – Run iOS and macOS on Non-Apple ARM64 Hardware Through UEFI

Skyloons: Balloon Pop Game

Show HN: Nekolike – a coin pusher roguelike you rebuild between floors

CAP theorem explained using Desi Metaphors

Sydney researchers uncover a hidden limit to AI predictability

Product managers are (expensive) search functions with taste

Ukraine's Fiber-Optic Drones Compete with Data Centers for Optical Fiber Supply

Show HN: pvewarden – let an AI agent patch Proxmox VMs without giving it a shell

The natural alliance of everyone else

Claude Fable 5.2, one day later [video]

29M Japanese Buildings

Theory predicting an older Universe passes key cosmological tests

Show HN: GuestVine – follow a person across every podcast they guest on

Show HN: Kafuck – Apache Kafka Rewritten in Brainfuck

Show HN: TeamOnly, free hosting for AI-built apps behind your company login

Show HN: Todaypad – a day planner that stores everything in the browser

Can a Dutch language model support journalists while preserving publicitations

Show HN: FileOctopus – Finder-style macOS file manager with split panes