aboutsummaryrefslogtreecommitdiff
path: root/ltable.c
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-11-13 13:37:24 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-11-13 13:37:24 -0300
commit2491b87c10db530eac2f3d81cd39f95875d16cd5 (patch)
tree56c066e5e2ccc3eb7b10bea1ba6c60d2b834a8f9 /ltable.c
parent0de81911525bc62bc2a8fc52a368102afed7022b (diff)
downloadlua-2491b87c10db530eac2f3d81cd39f95875d16cd5.tar.gz
lua-2491b87c10db530eac2f3d81cd39f95875d16cd5.tar.bz2
lua-2491b87c10db530eac2f3d81cd39f95875d16cd5.zip
New rule for size of array part
Array part needs 1/3 of its elements filled, instead of 1/2. Array entries use ~1/3 the memory of hash entries, so this new rule still ensures that array parts do not use more memory than keeping the values in the hash, while allowing more uses of the array part, which is more efficient than the hash.
Diffstat (limited to 'ltable.c')
-rw-r--r--ltable.c27
1 files changed, 20 insertions, 7 deletions
diff --git a/ltable.c b/ltable.c
index 3451445c..923f3eaa 100644
--- a/ltable.c
+++ b/ltable.c
@@ -471,12 +471,23 @@ typedef struct {
471 unsigned nums[MAXABITS + 1]; 471 unsigned nums[MAXABITS + 1];
472} Counters; 472} Counters;
473 473
474
475/*
476** Check whether it is worth to use 'na' array entries instead of 'nh'
477** hash nodes. (A hash node uses ~3 times more memory than an array
478** entry: Two values plus 'next' versus one value.) Evaluate with size_t
479** to avoid overflows.
480*/
481#define arrayXhash(na,nh) (cast_sizet(na) <= cast_sizet(nh) * 3)
482
474/* 483/*
475** Compute the optimal size for the array part of table 't'. 484** Compute the optimal size for the array part of table 't'.
485** This size maximizes the number of elements going to the array part
486** while satisfying the condition 'arrayXhash' with the use of memory if
487** all those elements went to the hash part.
476** 'ct->na' enters with the total number of array indices in the table 488** 'ct->na' enters with the total number of array indices in the table
477** and leaves with the number of keys that will go to the array part; 489** and leaves with the number of keys that will go to the array part;
478** return the optimal size. (The condition 'twotoi > 0' in the for loop 490** return the optimal size for the array part.
479** stops the loop if 'twotoi' overflows.)
480*/ 491*/
481static unsigned computesizes (Counters *ct) { 492static unsigned computesizes (Counters *ct) {
482 int i; 493 int i;
@@ -484,17 +495,19 @@ static unsigned computesizes (Counters *ct) {
484 unsigned int a = 0; /* number of elements smaller than 2^i */ 495 unsigned int a = 0; /* number of elements smaller than 2^i */
485 unsigned int na = 0; /* number of elements to go to array part */ 496 unsigned int na = 0; /* number of elements to go to array part */
486 unsigned int optimal = 0; /* optimal size for array part */ 497 unsigned int optimal = 0; /* optimal size for array part */
487 /* loop while keys can fill more than half of total size */ 498 /* traverse slices while 'twotoi' does not overflow and total of array
499 indices still can satisfy 'arrayXhash' against the array size */
488 for (i = 0, twotoi = 1; 500 for (i = 0, twotoi = 1;
489 twotoi > 0 && ct->na > twotoi / 2; 501 twotoi > 0 && arrayXhash(twotoi, ct->na);
490 i++, twotoi *= 2) { 502 i++, twotoi *= 2) {
491 a += ct->nums[i]; 503 unsigned nums = ct->nums[i];
492 if (a > twotoi/2) { /* more than half elements present? */ 504 a += nums;
505 if (nums > 0 && /* grows array only if it gets more elements... */
506 arrayXhash(twotoi, a)) { /* ...while using "less memory" */
493 optimal = twotoi; /* optimal size (till now) */ 507 optimal = twotoi; /* optimal size (till now) */
494 na = a; /* all elements up to 'optimal' will go to array part */ 508 na = a; /* all elements up to 'optimal' will go to array part */
495 } 509 }
496 } 510 }
497 lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal);
498 ct->na = na; 511 ct->na = na;
499 return optimal; 512 return optimal;
500} 513}