]> granicus.if.org Git - graphviz/commit
cgraph agxbuf: make inline strings the default
authorMatthew Fernandez <matthew.fernandez@gmail.com>
Sat, 10 Sep 2022 21:32:15 +0000 (14:32 -0700)
committerMatthew Fernandez <matthew.fernandez@gmail.com>
Wed, 21 Dec 2022 03:36:16 +0000 (19:36 -0800)
commit49df513ba741ca07de361039c9451d128415a63d
tree9a347905508e894ecb81ee1e2c8b81faeae34ab6
parent3a00bf0423dcf01cc8b0e071cb7f5cadbd441542
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`.
lib/cgraph/agxbuf.h