cgraph agxbuf: make inline strings the default
This change switches both `agxbinit` and zero-initialization (`agxbuf xb = {0}`)
to result in a buffer with inline storage. This means string data is written
inline until it becomes too large to store within the `agxbuf` struct itself,
when it is then relocated to the heap.
This is an optimization. Short dynamic strings can now be written completely
without heap allocation. For example, stringifying a number
(`agxbprint(&xb, "%d", i)`) will fit fully within the inline buffer.
Some performance evaluation comparing the merge-base of this series
(
740c4bf1edba931be0698de7bfde629eba2f40c0) to the current commit follows. These
numbers were derived using `/usr/bin/time` and Valgrind on `-O3 -flto -DNDEBUG`
builds of Graphviz. Instruction counts are provided for examples that are not
too long running.
┌────────┬────────────────────────────┬────────────────────────────┬──────┐
│ │ before │ after │ diff │
├────────┼────────────────────────────┼────────────────────────────┼──────┤
│ chain¹ │ 1.16s │ 1.05s │ -9% │
│ │
10436971652 instructions │
9006483829 instructions │ -14% │
│ │ 444MB peak RSS │ 180MB peak RSS │ -59% │
├────────┼────────────────────────────┼────────────────────────────┼──────┤
│ long² │ 2.69s │ 2.39s │ -11% │
│ │
22856315061 instructions │
19359309874 instructions │ -15% │
│ │ 1056MB peak RSS │ 416MB peak RSS │ -61% │
├────────┼────────────────────────────┼────────────────────────────┼──────┤
│ 456a³ │ 4h16m36s │ 4h13m46s │ -1% │
│ │ 881MB peak RSS │ 861MB peak RSS │ -2% │
├────────┼────────────────────────────┼────────────────────────────┼──────┤
│ 456b⁴ │ 3h57m41s │ 3h59m32s │ +1% │
│ │ 907MB peak RSS │ 886MB peak RSS │ -2% │
├────────┼────────────────────────────┼────────────────────────────┼──────┤
│ 1652a⁵ │ 17.98s │ 17.81s │ -1% │
│ │
113257927412 instructions │
113083410200 instructions │ -0% │
│ │ 97MB peak RSS │ 52MB peak RSS │ -46% │
├────────┼────────────────────────────┼────────────────────────────┼──────┤
│ 1652b⁶ │ 2m09s │ 2m08s │ -1% │
│ │
1697003634008 instructions │
1696880318663 instructions │ -0% │
│ │ 20MB peak RSS │ 16MB peak RSS │ -20% │
├────────┼────────────────────────────┼────────────────────────────┼──────┤
│ 1718⁷ │ 2m34s │ 2m35s │ +1% │
│ │
1620909322870 instructions │
1620889232022 instructions │ -0% │
│ │ 20MB peak RSS │ 18MB peak RSS │ -10% │
├────────┼────────────────────────────┼────────────────────────────┼──────┤
│ 1864a⁸ │ 32m05s │ 34m22s │ +7% │
│ │ 3435MB peak RSS │ 1479MB peak RSS │ -57% │
├────────┼────────────────────────────┼────────────────────────────┼──────┤
│ 1864b⁹ │ 14.68s │ 13.62s │ -7% │
│ │
89053964853 instructions │
83880586677 instructions │ -6% │
│ │ 2421MB peak RSS │ 464MB peak RSS │ -81% │
├────────┼────────────────────────────┼────────────────────────────┼──────┤
│ 2064¹⁰ │ 11m37s │ 11m38s │ +0% │
│ │
815499533953 instructions │
814007887571 instructions │ -0% │
│ │ 1370MB peak RSS │ 1261MB peak RSS │ -8% │
├────────┼────────────────────────────┼────────────────────────────┼──────┤
│ 2095¹¹ │ 2m10s │ 2m11s │ +1% │
│ │
74871386805 instructions │
74549569707 instructions │ -0% │
│ │ 113MB peak RSS │ 92MB peak RSS │ -19% │
└────────┴────────────────────────────┴────────────────────────────┴──────┘
Gitlab: closes #2302
¹ `dot -Tsvg -o /dev/null tests/regression_tests/large/long_chain`.
² “long” in the table is a graph generated by the following script:
print("digraph {")
for i in range(80000):
print(f" N{i} -> N{i + 1}")
print("}")
This represents something like a best case scenario to observe the effect of
this optimization. Lots of small unique strings. Run as
`dot -Tsvg -o /dev/null long.dot`.
³ The test case from https://gitlab.com/graphviz/graphviz/-/issues/456 run as
`dot -Tsvg -o /dev/null 456.dot`. Note that this actually errors out
eventually.
⁴ The test case from https://gitlab.com/graphviz/graphviz/-/issues/456 but with
`concentrate=true` removed. Run as `dot -Tsvg -o /dev/null 456.dot`.
⁵ The test case from https://gitlab.com/graphviz/graphviz/-/issues/1652 run as
`neato -Tsvg -o /dev/null 1652.dot`.
⁶ The test case from https://gitlab.com/graphviz/graphviz/-/issues/1652 run as
`dot -Tsvg -Gnslimit=2.0 -o /dev/null 1652.dot`. Note that this eventually
crashes.
⁷ swedish-flat.dot Magnus attached to
https://gitlab.com/graphviz/graphviz/-/issues/1718 run as
`circo -Tsvg -o /dev/null swedish-flag.dot`.
⁸ The test case from https://gitlab.com/graphviz/graphviz/-/issues/1864 run as
`neato -Tsvg -o /dev/null 1864.dot`.
⁹ The test case from https://gitlab.com/graphviz/graphviz/-/issues/1864 run as
`twopi -Tsvg -o /dev/null 1864.dot`.
¹⁰ The test case from https://gitlab.com/graphviz/graphviz/-/issues/2064 run as
`dot -Gnslimit=2 -Gnslimit1=2 -Gmaxiter=5000 -Tsvg -o /dev/null 2064.dot`.
¹¹The tests/2095.dot test case from prior to minimization
(
3819821ea70fae730dd224936628ed3929b03531). Run as
`dot -Tsvg -o /dev/null 2095.dot`.