From 203cbe7f6f53c5e95ebf4f870bb9dae53a0a5c72 Mon Sep 17 00:00:00 2001 From: "Duncan P. N. Exon Smith" Date: Sat, 27 Jun 2015 01:19:17 +0000 Subject: [PATCH] AsmPrinter: Document why DIEValueList uses a linked-list, NFC There are two main reasons why a linked-list makes sense for `DIEValueList`. 1. We want `DIE` to be on a `BumpPtrAllocator` to improve teardown efficiency. Making `DIEValueList` array-based would make that much more complicated. 2. The singly-linked list is fairly memory efficient. The histogram [1] shows that most DIEs have relatively few values, so we often pay less than the 2/3-pointer static overhead of a vector. Furthermore, we don't know ahead of time exactly how many values a `DIE` needs, so a vector-like scheme will on average over-allocate by ~50%. As it happens, that's the same memory overhead as the linked list node. [1]: http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-May/085910.html The comment I added to the code is a little more succinct, but I think it's enough to give the idea. llvm-svn: 240868 --- llvm/include/llvm/CodeGen/DIE.h | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/llvm/include/llvm/CodeGen/DIE.h b/llvm/include/llvm/CodeGen/DIE.h index 4170da0..f07712a 100644 --- a/llvm/include/llvm/CodeGen/DIE.h +++ b/llvm/include/llvm/CodeGen/DIE.h @@ -546,6 +546,16 @@ public: /// This is a singly-linked list, but instead of reversing the order of /// insertion, we keep a pointer to the back of the list so we can push in /// order. +/// +/// There are two main reasons to choose a linked list over a customized +/// vector-like data structure. +/// +/// 1. For teardown efficiency, we want DIEs to be BumpPtrAllocated. Using a +/// linked list here makes this way easier to accomplish. +/// 2. Carrying an extra pointer per \a DIEValue isn't expensive. 45% of DIEs +/// have 2 or fewer values, and 90% have 5 or fewer. A vector would be +/// over-allocated by 50% on average anyway, the same cost as the +/// linked-list node. class DIEValueList { struct Node : IntrusiveBackListNode { DIEValue V; -- 2.7.4