git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH] alloc.c: replace alloc by mempool

From
Stefan Beller <sbeller@google.com>
Date
May 3, 2018, 22:18 UTC
Message-ID
<20180503221802.61110-1-sbeller@google.com>
In-Reply-To
<BL0PR2101MB1106BA184260609DA69988A6CE870@BL0PR2101MB1106.namprd21.prod.outlook.com>
Signed-off-by: Stefan Beller <sbeller@google.com>
---
Show 12 quoted lines
>> The reason for my doubt is the potential quadratic behavior for new allocations,
>> in mem_pool_alloc() we walk all mp_blocks to see if we can fit the requested
>> allocation in one of the later blocks.
>> So if we call mem_pool_alloc a million times, we get a O(n) mp_blocks which
>> we'd have to walk in each call.
>
> With the current design, when a new mp_block is allocated, it is
> placed at the head of the linked list. This means that the most
> recently allocated mp_block is the 1st block that is
> searched. The *vast* majority of allocations should be fulfilled
> from this 1st block. It is only when the block is full that we
> search other mp_blocks in the list.

I just measured on git.git and linux.git (both of which are not *huge* by any standard, but should give a good indication. linux has 6M objects, and when allocating 1024 at a time, we run into the new block allocation ~6000 times).

I could not measure any meaningful difference.

linux.git $ git count-objects -v count: 0 size: 0 in-pack: 6036543 packs: 2 size-pack: 2492985 prune-packable: 0 garbage: 0 size-garbage: 0

(with this patch)
 Performance counter stats for '/u/git/git count-objects -v' (30 runs):
          2.123683      task-clock:u (msec)       #    0.831 CPUs utilized            ( +-  2.32% )
                 0      context-switches:u        #    0.000 K/sec                  
                 0      cpu-migrations:u          #    0.000 K/sec                  
               126      page-faults:u             #    0.059 M/sec                    ( +-  0.22% )
           895,900      cycles:u                  #    0.422 GHz                      ( +-  1.40% )
           976,596      instructions:u            #    1.09  insn per cycle           ( +-  0.01% )
           218,256      branches:u                #  102.772 M/sec                    ( +-  0.01% )
             8,331      branch-misses:u           #    3.82% of all branches          ( +-  0.61% )
       0.002556203 seconds time elapsed                                          ( +-  2.20% )
  Performance counter stats for 'git count-objects -v' (30 runs):
          2.410352      task-clock:u (msec)       #    0.801 CPUs utilized            ( +-  2.79% )
                 0      context-switches:u        #    0.000 K/sec                  
                 0      cpu-migrations:u          #    0.000 K/sec                  
               131      page-faults:u             #    0.054 M/sec                    ( +-  0.16% )
           993,301      cycles:u                  #    0.412 GHz                      ( +-  1.99% )
         1,087,428      instructions:u            #    1.09  insn per cycle           ( +-  0.02% )
           244,292      branches:u                #  101.351 M/sec                    ( +-  0.02% )
             9,264      branch-misses:u           #    3.79% of all branches          ( +-  0.57% )
       0.003010854 seconds time elapsed                                          ( +-  2.54% )

So I think we could just replace it for now and optimize again later, if it turns out to be a problem. I think the easiest optimisation is to increase the allocation size of having a lot more objects per mp_block.

Show 5 quoted lines
> If this is a concern, I think
> we have a couple low cost options to mitigate it (maybe a flag to
> control whether we search past the 1st mp_block for space, or
> logic to move blocks out of the search queue when they are
> full or fall below a threshold for available space).

Instead of a flag I thought of its own struct with its own functions, which would not just have a different searching behavior, but also store the size in the struct such that you can just call fixed_size_mem_pool_alloc(void) to get another pointer. A flag might be more elegant.

>
> If this is of interest, I could contribute a patch to enable one
> of these behaviors?
I am tempted to just do away with alloc.c for now and use the mem-pool.

Thanks, Stefan

 alloc.c | 60 +++++++++++----------------------------------------------
 1 file changed, 11 insertions(+), 49 deletions(-)
diff --git a/alloc.c b/alloc.c
index 12afadfacdd..bf003e161be 100644
--- a/alloc.c
+++ b/alloc.c
@@ -15,6 +15,7 @@
 #include "tree.h"
 #include "commit.h"
 #include "tag.h"
+#include "mem-pool.h"
 
 #define BLOCKING 1024
 
@@ -26,61 +27,39 @@ union any_object {
 	struct tag tag;
 };
 
-struct alloc_state {
-	int count; /* total number of nodes allocated */
-	int nr;    /* number of nodes left in current allocation */
-	void *p;   /* first free node in current allocation */
-};
-
-static inline void *alloc_node(struct alloc_state *s, size_t node_size)
-{
-	void *ret;
-
-	if (!s->nr) {
-		s->nr = BLOCKING;
-		s->p = xmalloc(BLOCKING * node_size);
-	}
-	s->nr--;
-	s->count++;
-	ret = s->p;
-	s->p = (char *)s->p + node_size;
-	memset(ret, 0, node_size);
-	return ret;
-}
-
-static struct alloc_state blob_state;
+static struct mem_pool blob_state = {NULL, sizeof(struct blob)*1024 - sizeof(struct mp_block), 0 };
 void *alloc_blob_node(void)
 {
-	struct blob *b = alloc_node(&blob_state, sizeof(struct blob));
+	struct blob *b = mem_pool_alloc(&blob_state, sizeof(struct blob));
 	b->object.type = OBJ_BLOB;
 	return b;
 }
 
-static struct alloc_state tree_state;
+static struct mem_pool tree_state = {NULL, sizeof(struct tree)*1024 - sizeof(struct mp_block), 0 };
 void *alloc_tree_node(void)
 {
-	struct tree *t = alloc_node(&tree_state, sizeof(struct tree));
+	struct tree *t = mem_pool_alloc(&tree_state, sizeof(struct tree));
 	t->object.type = OBJ_TREE;
 	return t;
 }
 
-static struct alloc_state tag_state;
+static struct mem_pool tag_state = {NULL, sizeof(struct tag)*1024 - sizeof(struct mp_block), 0 };
 void *alloc_tag_node(void)
 {
-	struct tag *t = alloc_node(&tag_state, sizeof(struct tag));
+	struct tag *t = mem_pool_alloc(&tag_state, sizeof(struct tag));
 	t->object.type = OBJ_TAG;
 	return t;
 }
 
-static struct alloc_state object_state;
+static struct mem_pool object_state = {NULL, sizeof(union any_object)*1024 - sizeof(struct mp_block), 0 };
 void *alloc_object_node(void)
 {
-	struct object *obj = alloc_node(&object_state, sizeof(union any_object));
+	struct object *obj = mem_pool_alloc(&object_state, sizeof(union any_object));
 	obj->type = OBJ_NONE;
 	return obj;
 }
 
-static struct alloc_state commit_state;
+static struct mem_pool commit_state = {NULL, sizeof(struct commit)*1024 - sizeof(struct mp_block), 0 };
 
 unsigned int alloc_commit_index(void)
 {
@@ -90,26 +69,9 @@ unsigned int alloc_commit_index(void)
 
 void *alloc_commit_node(void)
 {
-	struct commit *c = alloc_node(&commit_state, sizeof(struct commit));
+	struct commit *c = mem_pool_alloc(&commit_state, sizeof(struct commit));
 	c->object.type = OBJ_COMMIT;
 	c->index = alloc_commit_index();
 	return c;
 }
 
-static void report(const char *name, unsigned int count, size_t size)
-{
-	fprintf(stderr, "%10s: %8u (%"PRIuMAX" kB)\n",
-			name, count, (uintmax_t) size);
-}
-
-#define REPORT(name, type)	\
-    report(#name, name##_state.count, name##_state.count * sizeof(type) >> 10)
-
-void alloc_report(void)
-{
-	REPORT(blob, struct blob);
-	REPORT(tree, struct tree);
-	REPORT(commit, struct commit);
-	REPORT(tag, struct tag);
-	REPORT(object, union any_object);
-}

-- 
2.17.0.441.gb46fe60e1d-goog
Previous: Jameson MillerNext: Duy Nguyen
Message 38 of 100 in “Allocate cache entries from memory pool”
  1. 0/5 Allocate cache entries from memory poolJameson Miller, Apr 17, 2018
  2. 0/5 Allocate cache entries from memory poolJameson Miller, Apr 17, 2018
  3. 2/5 Add an API creating / discarding cache_entry structsJameson Miller, Apr 17, 2018
  4. Ben PeartApr 17, 2018
  5. 1/5 read-cache: teach refresh_cache_entry to take istateJameson Miller, Apr 17, 2018
  6. Ben PeartApr 17, 2018
  7. 3/5 mem-pool: fill out functionalityJameson Miller, Apr 17, 2018
  8. Jonathan TanApr 20, 2018
  9. Jameson MillerApr 23, 2018
  10. Jonathan TanApr 23, 2018
  11. Jameson MillerApr 23, 2018
  12. 5/5 Add optional memory validations around cache_entry lifecyleJameson Miller, Apr 17, 2018
  13. 4/5 Allocate cache entries from memory poolsJameson Miller, Apr 17, 2018
  14. Ben PeartApr 17, 2018
  15. Jameson MillerApr 23, 2018
  16. Junio C HamanoApr 18, 2018
  17. Stefan BellerApr 20, 2018
  18. Jameson MillerApr 23, 2018
  19. Stefan BellerApr 23, 2018
  20. Jameson MillerApr 23, 2018
  21. Jonathan TanApr 20, 2018
  22. Jameson MillerApr 23, 2018
  23. 0/5 Allocate cache entries from memory poolJameson Miller, Apr 30, 2018
  24. 1/5 read-cache: teach refresh_cache_entry() to take istateJameson Miller, Apr 30, 2018
  25. 3/5 mem-pool: fill out functionalityJameson Miller, Apr 30, 2018
  26. Stefan BellerApr 30, 2018
  27. Jameson MillerMay 1, 2018
  28. Duy NguyenMay 3, 2018
  29. 5/5 block alloc: add validations around cache_entry lifecyleJameson Miller, Apr 30, 2018
  30. Duy NguyenMay 3, 2018
  31. 2/5 block alloc: add lifecycle APIs for cache_entry structsJameson Miller, Apr 30, 2018
  32. 4/5 block alloc: allocate cache entries from mem_poolJameson Miller, Apr 30, 2018
  33. Duy NguyenMay 3, 2018
  34. Stefan BellerMay 3, 2018
  35. Duy NguyenMay 3, 2018
  36. Stefan BellerMay 3, 2018
  37. Jameson MillerMay 3, 2018
  38. alloc.c: replace alloc by mempoolStefan Beller, May 3, 2018
  39. Duy NguyenMay 4, 2018
  40. Junio C HamanoMay 8, 2018
  41. Stefan BellerMay 8, 2018
  42. Junio C HamanoMay 8, 2018
  43. 0/7 allocate cache entries from memory poolJameson Miller, May 23, 2018
  44. 1/7 read-cache: teach refresh_cache_entry() to take istateJameson Miller, May 23, 2018
  45. Stefan BellerMay 25, 2018
  46. 3/7 mem-pool: only search head block for available spaceJameson Miller, May 23, 2018
  47. 2/7 block alloc: add lifecycle APIs for cache_entry structsJameson Miller, May 23, 2018
  48. Junio C HamanoMay 24, 2018
  49. Jameson MillerMay 24, 2018
  50. 4/7 mem-pool: add lifecycle management functionsJameson Miller, May 23, 2018
  51. 5/7 mem-pool: fill out functionalityJameson Miller, May 23, 2018
  52. Stefan BellerJun 1, 2018
  53. 6/7 block alloc: allocate cache entries from mem_poolJameson Miller, May 23, 2018
  54. 7/7 block alloc: add validations around cache_entry lifecyleJameson Miller, May 23, 2018
  55. Junio C HamanoMay 24, 2018
  56. Jameson MillerMay 24, 2018
  57. Stefan BellerMay 25, 2018
  58. Jameson MillerJun 20, 2018
  59. Stefan BellerMay 25, 2018
  60. 0/8 Allocate cache entries from mem_poolJameson Miller, Jun 20, 2018
  61. 1/8 read-cache: teach refresh_cache_entry() to take istateJameson Miller, Jun 20, 2018
  62. 3/8 mem-pool: only search head block for available spaceJameson Miller, Jun 20, 2018
  63. Stefan BellerJun 21, 2018
  64. Jameson MillerJun 28, 2018
  65. 5/8 mem-pool: add lifecycle management functionsJameson Miller, Jun 20, 2018
  66. 8/8 block alloc: add validations around cache_entry lifecyleJameson Miller, Jun 20, 2018
  67. 7/8 block alloc: allocate cache entries from mem_poolJameson Miller, Jun 20, 2018
  68. 4/8 mem-pool: tweak math on mp_block allocation sizeJameson Miller, Jun 20, 2018
  69. 2/8 block alloc: add lifecycle APIs for cache_entry structsJameson Miller, Jun 20, 2018
  70. Stefan BellerJun 21, 2018
  71. Jameson MillerJun 28, 2018
  72. 6/8 mem-pool: fill out functionalityJameson Miller, Jun 20, 2018
  73. 0/8 Allocate cache entries from mem_poolJameson Miller, Jun 28, 2018
  74. 2/8 read-cache: make_cache_entry should take object_id structJameson Miller, Jun 28, 2018
  75. Junio C HamanoJun 28, 2018
  76. SZEDER GáborJun 28, 2018
  77. 3/8 block alloc: add lifecycle APIs for cache_entry structsJameson Miller, Jun 28, 2018
  78. Junio C HamanoJun 28, 2018
  79. SZEDER GáborJun 28, 2018
  80. 5/8 mem-pool: add life cycle management functionsJameson Miller, Jun 28, 2018
  81. Junio C HamanoJun 28, 2018
  82. 4/8 mem-pool: only search head block for available spaceJameson Miller, Jun 28, 2018
  83. 6/8 mem-pool: fill out functionalityJameson Miller, Jun 28, 2018
  84. Junio C HamanoJun 28, 2018
  85. Jameson MillerJul 2, 2018
  86. 8/8 block alloc: add validations around cache_entry lifecyleJameson Miller, Jun 28, 2018
  87. 1/8 read-cache: teach refresh_cache_entry() to take istateJameson Miller, Jun 28, 2018
  88. 7/8 block alloc: allocate cache entries from mem-poolJameson Miller, Jun 28, 2018
  89. 0/8 Allocate cache entries from mem_poolJameson Miller, Jul 2, 2018
  90. 2/8 read-cache: teach make_cache_entry to take object_idJameson Miller, Jul 2, 2018
  91. Stefan BellerJul 2, 2018
  92. Jameson MillerJul 5, 2018
  93. 3/8 block alloc: add lifecycle APIs for cache_entry structsJameson Miller, Jul 2, 2018
  94. Duy NguyenJul 22, 2018
  95. 4/8 mem-pool: only search head block for available spaceJameson Miller, Jul 2, 2018
  96. 5/8 mem-pool: add life cycle management functionsJameson Miller, Jul 2, 2018
  97. 7/8 block alloc: allocate cache entries from mem_poolJameson Miller, Jul 2, 2018
  98. 8/8 block alloc: add validations around cache_entry lifecyleJameson Miller, Jul 2, 2018
  99. 6/8 mem-pool: fill out functionalityJameson Miller, Jul 2, 2018
  100. 1/8 read-cache: teach refresh_cache_entry to take istateJameson Miller, Jul 2, 2018

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.