1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
From c3c12e1b4ff908211b156a182a5027f2b11b0709 Mon Sep 17 00:00:00 2001
From: Maria Matejka <mq@ucw.cz>
Date: Tue, 24 Dec 2024 16:16:55 +0100
Subject: [PATCH] Allocate the normalization buckets on stack
Even though allocating from tmp_linpool is quite cheap,
it isn't cheap when the block is larger than a page, which is the case here.
Instead, we now allocate just the result which typically fits in a page,
avoiding a necessity of a malloc().
---
nest/rt-attr.c | 37 ++++++++++++++++++++++++-------------
1 file changed, 24 insertions(+), 13 deletions(-)
diff --git a/nest/rt-attr.c b/nest/rt-attr.c
index 8d651efb2..9d5e10980 100644
--- nest/rt-attr.c
+++ nest/rt-attr.c
@@ -967,8 +967,8 @@ ea_list_size(ea_list *o)
* and creates the final structure useful for storage or fast searching.
* The method is a bucket sort.
*
- * Returns the final ea_list with some excess memory at the end,
- * allocated from the tmp_linpool. The adata is linked from the original places.
+ * Returns the final ea_list allocated from the tmp_linpool.
+ * The adata is linked from the original places.
*/
ea_list *
ea_normalize(ea_list *e, u32 upto)
@@ -976,21 +976,17 @@ ea_normalize(ea_list *e, u32 upto)
/* We expect some work to be actually needed. */
ASSERT_DIE(!BIT32_TEST(&upto, e->stored));
- /* Allocate the output */
- ea_list *out = tmp_allocz(ea_class_max * sizeof(eattr) + sizeof(ea_list));
- *out = (ea_list) {
- .flags = EALF_SORTED,
- };
-
+ /* Allocate the buckets locally */
+ eattr *buckets = allocz(ea_class_max * sizeof(eattr));
uint min_id = ~0, max_id = 0;
- eattr *buckets = out->attrs;
+ ea_list *next = NULL;
/* Walk the attribute lists, one after another. */
for (; e; e = e->next)
{
- if (!out->next && BIT32_TEST(&upto, e->stored))
- out->next = e;
+ if (!next && BIT32_TEST(&upto, e->stored))
+ next = e;
for (int i = 0; i < e->count; i++)
{
@@ -1000,7 +996,7 @@ ea_normalize(ea_list *e, u32 upto)
if (id < min_id)
min_id = id;
- if (out->next)
+ if (next)
{
/* Underlay: check whether the value is duplicate */
if (buckets[id].id && buckets[id].fresh)
@@ -1026,6 +1022,18 @@ ea_normalize(ea_list *e, u32 upto)
}
}
+ /* Find out how big the output actually is. */
+ uint len = 0;
+ for (uint id = min_id; id <= max_id; id++)
+ if (buckets[id].id && !(buckets[id].undef && buckets[id].fresh))
+ len++;
+
+ ea_list *out = tmp_alloc(sizeof(ea_list) + len * sizeof(eattr));
+ *out = (ea_list) {
+ .flags = EALF_SORTED,
+ .next = next,
+ };
+
/* And now we just walk the list from beginning to end and collect
* everything to the beginning of the list.
* Walking just that part which is inhabited for sure. */
@@ -1044,9 +1052,12 @@ ea_normalize(ea_list *e, u32 upto)
/* Move the attribute to the beginning */
ASSERT_DIE(out->count < id);
- buckets[out->count++] = buckets[id];
+ ASSERT_DIE(out->count < len);
+ out->attrs[out->count++] = buckets[id];
}
+ ASSERT_DIE(out->count == len);
+
/* We want to bisect only if the list is long enough */
if (out->count > 5)
out->flags |= EALF_BISECT;
--
GitLab
|
