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?

Git Submodules as a Package Manager

Show HN: Wordle for Memecoins

MicroEMACS

HN is temporarily blocking Show HN posts from your account

Show HN: Unitpost/email – open-source Email Components and Layouts

Ethical AI that respects privacy and the planet

AI Mobile App Development Company: Services and Platform Guide – Kellton

What If Your Notes Could Calculate? Introducing ANQL

Higher Multipoles of the Cow

Generating Bitcoin wallet seed phrases from playing cards

Show HN: Rxlab market – a research agent for stocks market

Substantial under-detection of human rabies cases in the United States

A Comprehensive Study of Native Code Bugs in Python Applications

Infinite Slop: An endless AI-generated TV channel

Stonehenge – From Restoration to Conservation

CAA Has Been Mandatory Since 2017 but 93.1% of Company Domains Skip It

Russian missile uses Nvidia AI chip to help target Ukraine

Rustc_codegen_JVM: Compile Rust to Java bytecode and runnable JARs

The economics come before the code: architecting a real-time pipeline

Google Maps renames "Lake Ontario" to "Lake America" faster than US Government

Is it just me, or has Claude Opus gotten worse recently?

Two months too late (Linux kernel 1day)

Operation Binder: Secrets of Inter-Process Communication [video]

Stanisław Lem foretold the current LLM mania in 1964

Fal.live – AI television directed by everyone

Show HN: ChooseCompute – Clean NAS and hard drive database for AI

Helius – Personal Finance in One SQLite File, with a Rust CLI and TUI

Trading Journal for Trade Tracking and Performance Analysis|TradeBB

One trie, three jobs, zero benchmarks won

Reducing Java memory usage by 43% with joint JVM and container tuning