)]}' { "commit": "28044bc7e33163392d723b5d7bbe353a089108fb", "tree": "b9576f5600507019f5e9db9c327773b67a12458e", "parents": [ "eb0c7518b080c93305d0060e91c2bca519cff6ed" ], "author": { "name": "David \u0027Digit\u0027 Turner", "email": "digit@google.com", "time": "Thu Nov 28 16:39:43 2019 +0100" }, "committer": { "name": "Commit Bot", "email": "commit-bot@chromium.org", "time": "Tue Feb 04 23:40:44 2020 +0000" }, "message": "Speed up source file set operations.\n\nProfiling the Fuchsia Zircon build\u0027s \"gn gen\" operation [1] shows\nthat a lot of time is spend copying source file sets during\na very large number of scope merges.\n\nThis CL provides a 30% speedup for the Zircon \"gn gen\", without\ndegrading the Chromium one (see measurements below). This is done\nby introducing SourceFileSet, a dedicated data type with avoids\nstd::string allocations, and has much faster lookup and insert /\ncopy operations, compared with std::set\u003cSourceFileSet\u003e\n\nMore precisely, by:\n\n - Introducing a StringAtom data type, modelling a pointer to\n a globally unique constant string, with a heavily optimized\n lookup implementation. See comments in src/gn/string_atom.h\n and src/gn/string_atom.cc for usage and full details.\n\n - Modifying SourceFile to use a StringAtom, instead of an\n std::string to store the file path. This reduces the size\n and copy cost of each instance.\n\n - Replace std::set\u003cSourceFile\u003e with the new SourceFileSet data\n type (defined as a base::flat_set\u003cSourceFile\u003e, with fast\n pointer-based comparisons, which turns out to be significantly\n faster than other alternatives).\n\nNote that this works well because source file paths are immutable\nand shared among many many scopes / SourceFileSet instances.\n\nNote that despite the fact that SourceFileSet is unordered for\nperformance reasons, this CL does not modify the outputs of\n\"gn gen\", at least when used for a Chromium Linux build. See [3]\nfor the methodology used to verify that.\n\nFinally note that the patch reduces memory usage by nearly 1 GiB (!!)\nfor the Zircon build [4] (but only 6 MiB for the Chromium one).\n\n[1] Performed from a Fuchsia source workspace with:\n $ gn gen --root\u003dzircon out/default.zircon\n\n[2] Results comparing the performance of \u0027gn\u0027 before and\n after the patch. Both binaries were built with a recent\n clang toolchain with build/gen.py -use-icf -use-lto:\n\n--------------------------------------------------------\n// ZIRCON BUILD\n\n[fuchsia] $ gn gen --root\u003dzircon out/default.zircon\n\n//// BEFORE (* \u003d best of 5 runs)\n\nDone. Made 51431 targets from 944 files in 12825ms *\nDone. Made 51431 targets from 944 files in 13932ms\nDone. Made 51431 targets from 944 files in 14886ms\nDone. Made 51431 targets from 944 files in 14642ms\nDone. Made 51431 targets from 944 files in 13548ms\n\n//// AFTER (* \u003d best of 5 runs)\n\nDone. Made 51431 targets from 944 files in 10623ms\nDone. Made 51431 targets from 944 files in 10185ms\nDone. Made 51431 targets from 944 files in 10623ms\nDone. Made 51431 targets from 944 files in 9759ms *\nDone. Made 51431 targets from 944 files in 10656ms\n\nOverall improvement: 12825 - 9759 \u003d 3066 ms (31% faster)\n\n--------------------------------------------------------\n// CHROMIUM BUILD\n\n[chromium/src] $ gn gen out/default\n\n//// BEFORE\nDone. Made 12150 targets from 2121 files in 4319ms\nDone. Made 12150 targets from 2121 files in 4545ms\nDone. Made 12150 targets from 2121 files in 4346ms\nDone. Made 12150 targets from 2121 files in 4298ms *\nDone. Made 12150 targets from 2121 files in 4390ms\n\n//// AFTER\nDone. Made 12150 targets from 2121 files in 4274ms\nDone. Made 12150 targets from 2121 files in 4223ms\nDone. Made 12150 targets from 2121 files in 4098ms\nDone. Made 12150 targets from 2121 files in 4419ms\nDone. Made 12150 targets from 2121 files in 4096ms *\n\nOverall improvement: 4298 - 4096 \u003d 202 ms (4.9% faster)\n\n[3] To verify that \"gn gen\" outputs were not affected\nby this CL, the following experiment was setup on a\nLinux workstation.\n\n 1) Create a fresh chromium source checkout on\n a btrfs subvolume directory (e.g. /work/chromium,\n where /work is a btrfs mount point).\n\n 2) cd /work/chromium/src \u0026\u0026 touch out/args.gn\n # Create an empty args.gn there.\n\n 3) cd /work/chromium/src \u0026\u0026 \u003coriginal-gn\u003e gen out\n # Generate out/ files using original gn program.\n\n 4) cd /work \u0026\u0026\n sudo btrfs subvolume snapshot chromium chromium-original\n # Snapshot the generated state to /work/chromium-original\n\n 4) cd /work/chromium/src \u0026\u0026 \u003cnew-gn\u003e gen out\n # Regenerate out/ files using patched gn program.\n\n 5) diff -burN /work/chromium-original/src/out /work/chromium/src/out\n # Compare the files under out/\n\n --- /work/chromium0/src/out/default/build.ninja\t2020-01-31 13:24:32.643343218 +0100\n +++ /work/cr-xx0/src/out/default/build.ninja\t2020-01-31 13:21:42.105117112 +0100\n @@ -1,7 +1,7 @@\n ninja_required_version \u003d 1.7.2\n\n rule gn\n - command \u003d ../../../../../tmp/gn-sourcefileset --root\u003d../.. -q gen .\n + command \u003d ../../../../../tmp/gn-master --root\u003d../.. -q gen .\n description \u003d Regenerating ninja files\n\n build build.ninja: gn\n\nThe result shows that the only difference is the name of \"gn\"\nexecutable name captured in build.ninja, all other files being\nidentical.\n\n[4] Peak resident set size (RSS) usage as reported with /usr/bin/time -v\n\n// ZIRCON BUILD\n\nBEFORE: Maximum resident set size (kbytes): 2793824\nAFTER: Maximum resident set size (kbytes): 1817880\nDIFF: 2793824 - 1817880 \u003d 975944 kiB \u003d 953 MiB (!!)\n\n// CHROMIUM BUILD\n\nBEFORE: Maximum resident set size (kbytes): 544296\nAFTER: Maximum resident set size (kbytes): 538068\nDIFF: 544296 - 538068 \u003d 6228 kiB \u003d 6.1 MiB\n\nChange-Id: I4f11fcddeb7b84a6126b748d2b4d66afd1642545\nReviewed-on: https://gn-review.googlesource.com/c/gn/+/7280\nCommit-Queue: Brett Wilson \u003cbrettw@chromium.org\u003e\nReviewed-by: Brett Wilson \u003cbrettw@chromium.org\u003e\nReviewed-by: Scott Graham \u003cscottmg@chromium.org\u003e\n", "tree_diff": [ { "type": "modify", "old_id": "592e65f91ac09c9be0f259c4e5a17491f2dc24fc", "old_mode": 33261, "old_path": "build/gen.py", "new_id": "534cf5d3dfe23c72712c540afa60c8d1eed6e6df", "new_mode": 33261, "new_path": "build/gen.py" }, { "type": "modify", "old_id": "a110771e7c16af051939f909629e51aa3ae179bd", "old_mode": 33188, "old_path": "src/gn/analyzer.cc", "new_id": "18563b87724c3e5fa886aba4d01a64d4e24cbef0", "new_mode": 33188, "new_path": "src/gn/analyzer.cc" }, { "type": "modify", "old_id": "cf9f409871c5b1e82070a57bddd5c715656eabff", "old_mode": 33188, "old_path": "src/gn/analyzer.h", "new_id": "2ffdb527038e8ce49e4003c8e85160b5f4be583c", "new_mode": 33188, "new_path": "src/gn/analyzer.h" }, { "type": "modify", "old_id": "5ba924b6a5c9264f0cc6d912d8d7ac254bd0574e", "old_mode": 33188, "old_path": "src/gn/args.h", "new_id": "992d48f18dd3dd12dbb10eb81ca7023ea4bf7a90", "new_mode": 33188, "new_path": "src/gn/args.h" }, { "type": "modify", "old_id": "9708df3bdb3fe4a53840f44ce75f2abd48807fe7", "old_mode": 33188, "old_path": "src/gn/build_settings.h", "new_id": "0bb55e9d84328a8bf35c5f8b63b485f7bf41be59", "new_mode": 33188, "new_path": "src/gn/build_settings.h" }, { "type": "modify", "old_id": "2793de7e60d4ca9a6847ec7ebb63bf03a03fd325", "old_mode": 33188, "old_path": "src/gn/config.cc", "new_id": "c0a516665103e88644192850362bcff9b2e0296a", "new_mode": 33188, "new_path": "src/gn/config.cc" }, { "type": "modify", "old_id": "8dcedefbbd5c675f40ae62e963fae8160ea17bfb", "old_mode": 33188, "old_path": "src/gn/config.h", "new_id": "cb208d1b66d8a2f9596043e8ac59b6d21705be2c", "new_mode": 33188, "new_path": "src/gn/config.h" }, { "type": "modify", "old_id": "aec84092a18cf9e165a9d8651e94cfeb1981f647", "old_mode": 33188, "old_path": "src/gn/function_exec_script.cc", "new_id": "20bd81582fdde67f758ca9c9c367cd3625d7538b", "new_mode": 33188, "new_path": "src/gn/function_exec_script.cc" }, { "type": "modify", "old_id": "308d1e20ca4fb306ae72069488d42a44e597ab99", "old_mode": 33188, "old_path": "src/gn/item.cc", "new_id": "3a3a166b36c606665cd7f6bf48facd2a0aeef1cd", "new_mode": 33188, "new_path": "src/gn/item.cc" }, { "type": "modify", "old_id": "d53d9edec59a3cda77f5231529e64dd59a99abe0", "old_mode": 33188, "old_path": "src/gn/item.h", "new_id": "2942a665fd24fdf934d62564cebbfad646447f5a", "new_mode": 33188, "new_path": "src/gn/item.h" }, { "type": "modify", "old_id": "62207902c1249b249145f9758dc906d86b847ff7", "old_mode": 33188, "old_path": "src/gn/ninja_create_bundle_target_writer.cc", "new_id": "efb896ac6f96c6bad274d718c2ed4d2f55471ebb", "new_mode": 33188, "new_path": "src/gn/ninja_create_bundle_target_writer.cc" }, { "type": "modify", "old_id": "edfc87f6cf16b3b0100e71130752214942f95915", "old_mode": 33188, "old_path": "src/gn/scope.h", "new_id": "c5dcd38abf2fa933c45235488d1f86312dd1069a", "new_mode": 33188, "new_path": "src/gn/scope.h" }, { "type": "modify", "old_id": "57ef5ee910286fb9c65f126ba85f97b6476d9926", "old_mode": 33188, "old_path": "src/gn/setup.cc", "new_id": "5d7bc8a5a3d16360ff0f929b85d9e962adcce7d7", "new_mode": 33188, "new_path": "src/gn/setup.cc" }, { "type": "modify", "old_id": "acb1c480d93e1611c09dc3048cbe9a02b85a9530", "old_mode": 33188, "old_path": "src/gn/source_file.cc", "new_id": "1dacbfa1f56ce26e06a9cc591db6c50e79d2a83f", "new_mode": 33188, "new_path": "src/gn/source_file.cc" }, { "type": "modify", "old_id": "392cdd449f3374a016c1049a9b2a5392dd5cd1f1", "old_mode": 33188, "old_path": "src/gn/source_file.h", "new_id": "d7ed06e63c510fc69fb956ea7815a96f9cc72e74", "new_mode": 33188, "new_path": "src/gn/source_file.h" }, { "type": "add", "old_id": "0000000000000000000000000000000000000000", "old_mode": 0, "old_path": "/dev/null", "new_id": "c310ffd8b28cccb952fcc37bf940d3a5264b3f16", "new_mode": 33188, "new_path": "src/gn/string_atom.cc" }, { "type": "add", "old_id": "0000000000000000000000000000000000000000", "old_mode": 0, "old_path": "/dev/null", "new_id": "fa92ac2db36165683791950fecd29367c9c1af1c", "new_mode": 33188, "new_path": "src/gn/string_atom.h" }, { "type": "add", "old_id": "0000000000000000000000000000000000000000", "old_mode": 0, "old_path": "/dev/null", "new_id": "2dcc99381a8e435a3be9d2c626eb34492c7f1e7d", "new_mode": 33188, "new_path": "src/gn/string_atom_unittest.cc" }, { "type": "modify", "old_id": "0b5402e174fbbded8667552bd1790437aa444290", "old_mode": 33188, "old_path": "src/gn/target.cc", "new_id": "8721f1a994e446cc89597c2f540ec8f82334c3a2", "new_mode": 33188, "new_path": "src/gn/target.cc" }, { "type": "modify", "old_id": "fbe0f716c37ffda26d200f9b1abbc931a60cd5dd", "old_mode": 33188, "old_path": "src/gn/target.h", "new_id": "3c7ebf9bfd21902ae798ce4c8867bc83fb03edeb", "new_mode": 33188, "new_path": "src/gn/target.h" }, { "type": "modify", "old_id": "d66b4893e5c527534ba3d735f4cecb6e1e25c336", "old_mode": 33188, "old_path": "src/gn/toolchain.cc", "new_id": "bfad81db6351b35a194f483fb74e67330d621472", "new_mode": 33188, "new_path": "src/gn/toolchain.cc" }, { "type": "modify", "old_id": "6e450a1b126c5082fc89b6c490ba2e4a6baed78b", "old_mode": 33188, "old_path": "src/gn/toolchain.h", "new_id": "eb5a60c526ecdc3473adb10b4c84aca36b710a0d", "new_mode": 33188, "new_path": "src/gn/toolchain.h" } ] }