Mercurial > vim
comparison src/hashtab.c @ 17508:34966be2e856 v8.1.1752
patch 8.1.1752: resizing hashtable is inefficient
commit https://github.com/vim/vim/commit/7b73d7ebf71c9148c90a500116f25ec2314c7273
Author: Bram Moolenaar <Bram@vim.org>
Date: Fri Jul 26 21:26:34 2019 +0200
patch 8.1.1752: resizing hashtable is inefficient
Problem: Resizing hashtable is inefficient.
Solution: Avoid resizing when the final size is predictable.
| author | Bram Moolenaar <Bram@vim.org> |
|---|---|
| date | Fri, 26 Jul 2019 21:30:06 +0200 |
| parents | ce04ebdf26b8 |
| children | f0f9692d4487 |
comparison
equal
deleted
inserted
replaced
| 17507:b64a5a737a7c | 17508:34966be2e856 |
|---|---|
| 284 hash_lock(hashtab_T *ht) | 284 hash_lock(hashtab_T *ht) |
| 285 { | 285 { |
| 286 ++ht->ht_locked; | 286 ++ht->ht_locked; |
| 287 } | 287 } |
| 288 | 288 |
| 289 #if 0 /* currently not used */ | |
| 290 /* | 289 /* |
| 291 * Lock a hashtable at the specified number of entries. | 290 * Lock a hashtable at the specified number of entries. |
| 292 * Caller must make sure no more than "size" entries will be added. | 291 * Caller must make sure no more than "size" entries will be added. |
| 293 * Must call hash_unlock() later. | 292 * Must call hash_unlock() later. |
| 294 */ | 293 */ |
| 296 hash_lock_size(hashtab_T *ht, int size) | 295 hash_lock_size(hashtab_T *ht, int size) |
| 297 { | 296 { |
| 298 (void)hash_may_resize(ht, size); | 297 (void)hash_may_resize(ht, size); |
| 299 ++ht->ht_locked; | 298 ++ht->ht_locked; |
| 300 } | 299 } |
| 301 #endif | |
| 302 | 300 |
| 303 /* | 301 /* |
| 304 * Unlock a hashtable: allow ht_array changes again. | 302 * Unlock a hashtable: allow ht_array changes again. |
| 305 * Table will be resized (shrink) when necessary. | 303 * Table will be resized (shrink) when necessary. |
| 306 * This must balance a call to hash_lock(). | 304 * This must balance a call to hash_lock(). |
| 366 else | 364 else |
| 367 minsize = ht->ht_used * 4; /* make plenty of room */ | 365 minsize = ht->ht_used * 4; /* make plenty of room */ |
| 368 } | 366 } |
| 369 else | 367 else |
| 370 { | 368 { |
| 371 /* Use specified size. */ | 369 // Use specified size. |
| 372 if ((long_u)minitems < ht->ht_used) /* just in case... */ | 370 if ((long_u)minitems < ht->ht_used) // just in case... |
| 373 minitems = (int)ht->ht_used; | 371 minitems = (int)ht->ht_used; |
| 374 minsize = minitems * 3 / 2; /* array is up to 2/3 full */ | 372 minsize = (minitems * 3 + 1) / 2; // array is up to 2/3 full |
| 375 } | 373 } |
| 376 | 374 |
| 377 newsize = HT_INIT_SIZE; | 375 newsize = HT_INIT_SIZE; |
| 378 while (newsize < minsize) | 376 while (newsize < minsize) |
| 379 { | 377 { |