Understanding memory footprint of a simple recursive program

I am trying to understand heap memory usage of a simple differential computation. It uses
way more memory than I can explain and I want to figure out if there is a way to
reduce its footprint.

Specifically, I have the following trivial Datalog program compiled to DD using
DDlog:

Span(entity, label) :- Labeled(entity, label).
Span(parent, label) :- Dependency(child, parent), Span(child, label).

It starts with a set of labeled nodes and propagates labels along Dependency edges. I am not
showing DD code, as it is automatically generated and not easy to read. I use the recursive
variable
that I borrowed from Frank's code some time ago for the recursive Span collection. If my
cost model of DD is correct, the resulting dataflow only has three operators that consume
memory:

• arrangement of Span using the first column as a key (needed for the second rule)
• by-self arrangement of Span created by the distinct operator in Variable::drop()
• group_arranged() created inside the same distinct operator

There is also an arrangement of the Dependency relation from the seconds rule, but it is negligibly
small compared to Span.

I use a simple
profiler
to measure peak size of these operators throughout the run on a customer dataset. Here is what I get:

• Span.arrange_by_key(): 8,573,578 records
• Span.arrange_by_self(): 8,682,860 records
• Span.group_arranged: 8,573,578 records

The size of the data type I use to represent values is 16 bytes. The by-key arrangement has two
values (k,v), so, not counting metadata, there are approximately 26,000,000 16-byte values or
400MB of actual data in the program at the peak.

Using massif, I observe that
the actual peak amount of memory that DD allocated on the heap is 1.6GB, including

• 800MB in group_arranged (the exact site where memory gets allocated is
  OrderedBuilder::with_capacity())
• 800MB in Buffer::flush(), Exchange::flush(), Counter::push(), which, I guess, should be
  accounted to the two arrangements of Span.

(note, this is the actual memory requested by DD, not counting padding and malloc metadata).

The former is particularly interesting. Assuming my interpretation of profiling data is correct,
DD uses 800MB to store 8,5M records, or ~100 bytes per record in group_arranged.

I would appreciate any help in:

• understanding these overheads
• figuring out if there is a more memory-efficient way to encode the same computation in DD
• any hints on whether DD could offer a more memory-efficient implementation of these operators,
  potentially at the cost of some loss in incremental performance

Thanks!

Start with the recursive variable implementation in rust/template/differential_datalog/variable.rs and the profiler in rust/template/differential_datalog/profile.rs. Trace the allocations reported in OrderedBuilder::with_capacity(), Buffer::flush(), Exchange::flush(), and Counter::push(), then compare them with the reported arrangement sizes. Done means explaining the memory overhead or identifying a concrete memory-saving change for this computation.