Skip to content

Commit 6c0041e

Browse files
MaxGraeydcodeIO
MaxGraey
authored and
dcodeIO
committed
Use integer fractions for Map/Set FILL_FACTOR/FREE_FACTOR (AssemblyScript#903)
1 parent e5c1e08 commit 6c0041e

File tree

8 files changed

+512
-496
lines changed

8 files changed

+512
-496
lines changed

‎std/assembly/map.ts‎

Lines changed: 13 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -11,11 +11,19 @@ const INITIAL_CAPACITY = 4;
1111

1212
// @ts-ignore: decorator
1313
@inline
14-
const FILL_FACTOR: f64 = 8 / 3;
14+
const FILL_FACTOR_N = 8;
1515

1616
// @ts-ignore: decorator
1717
@inline
18-
const FREE_FACTOR: f64 = 3 / 4;
18+
const FILL_FACTOR_D = 3;
19+
20+
// @ts-ignore: decorator
21+
@inline
22+
const FREE_FACTOR_N = 3;
23+
24+
// @ts-ignore: decorator
25+
@inline
26+
const FREE_FACTOR_D = 4;
1927

2028
/** Structure of a map entry. */
2129
@unmanaged class MapEntry<K,V> {
@@ -122,7 +130,7 @@ export class Map<K,V> {
122130
// check if rehashing is necessary
123131
if (this.entriesOffset == this.entriesCapacity) {
124132
this.rehash(
125-
this.entriesCount < <i32>(this.entriesCapacity * FREE_FACTOR)
133+
this.entriesCount < this.entriesCapacity * FREE_FACTOR_N / FREE_FACTOR_D
126134
? this.bucketsMask // just rehash if 1/4+ entries are empty
127135
: (this.bucketsMask << 1) | 1 // grow capacity to next 2^N
128136
);
@@ -156,15 +164,15 @@ export class Map<K,V> {
156164
var halfBucketsMask = this.bucketsMask >> 1;
157165
if (
158166
halfBucketsMask + 1 >= max<u32>(INITIAL_CAPACITY, this.entriesCount) &&
159-
this.entriesCount < <i32>(this.entriesCapacity * FREE_FACTOR)
167+
this.entriesCount < this.entriesCapacity * FREE_FACTOR_N / FREE_FACTOR_D
160168
) this.rehash(halfBucketsMask);
161169
return true;
162170
}
163171

164172
private rehash(newBucketsMask: u32): void {
165173
var newBucketsCapacity = <i32>(newBucketsMask + 1);
166174
var newBuckets = new ArrayBuffer(newBucketsCapacity * <i32>BUCKET_SIZE);
167-
var newEntriesCapacity = <i32>(newBucketsCapacity * FILL_FACTOR);
175+
var newEntriesCapacity = newBucketsCapacity * FILL_FACTOR_N / FILL_FACTOR_D;
168176
var newEntries = new ArrayBuffer(newEntriesCapacity * <i32>ENTRY_SIZE<K,V>());
169177

170178
// copy old entries to new entries

‎std/assembly/set.ts‎

Lines changed: 13 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -10,11 +10,19 @@ const INITIAL_CAPACITY = 4;
1010

1111
// @ts-ignore: decorator
1212
@inline
13-
const FILL_FACTOR: f64 = 8 / 3;
13+
const FILL_FACTOR_N = 8;
1414

1515
// @ts-ignore: decorator
1616
@inline
17-
const FREE_FACTOR: f64 = 3 / 4;
17+
const FILL_FACTOR_D = 3;
18+
19+
// @ts-ignore: decorator
20+
@inline
21+
const FREE_FACTOR_N = 3;
22+
23+
// @ts-ignore: decorator
24+
@inline
25+
const FREE_FACTOR_D = 4;
1826

1927
/** Structure of a set entry. */
2028
@unmanaged class SetEntry<K> {
@@ -100,7 +108,7 @@ export class Set<T> {
100108
// check if rehashing is necessary
101109
if (this.entriesOffset == this.entriesCapacity) {
102110
this.rehash(
103-
this.entriesCount < <i32>(this.entriesCapacity * FREE_FACTOR)
111+
this.entriesCount < this.entriesCapacity * FREE_FACTOR_N / FREE_FACTOR_D
104112
? this.bucketsMask // just rehash if 1/4+ entries are empty
105113
: (this.bucketsMask << 1) | 1 // grow capacity to next 2^N
106114
);
@@ -134,15 +142,15 @@ export class Set<T> {
134142
var halfBucketsMask = this.bucketsMask >> 1;
135143
if (
136144
halfBucketsMask + 1 >= max<u32>(INITIAL_CAPACITY, this.entriesCount) &&
137-
this.entriesCount < <i32>(this.entriesCapacity * FREE_FACTOR)
145+
this.entriesCount < this.entriesCapacity * FREE_FACTOR_N / FREE_FACTOR_D
138146
) this.rehash(halfBucketsMask);
139147
return true;
140148
}
141149

142150
private rehash(newBucketsMask: u32): void {
143151
var newBucketsCapacity = <i32>(newBucketsMask + 1);
144152
var newBuckets = new ArrayBuffer(newBucketsCapacity * <i32>BUCKET_SIZE);
145-
var newEntriesCapacity = <i32>(newBucketsCapacity * FILL_FACTOR);
153+
var newEntriesCapacity = newBucketsCapacity * FILL_FACTOR_N / FILL_FACTOR_D;
146154
var newEntries = new ArrayBuffer(newEntriesCapacity * <i32>ENTRY_SIZE<T>());
147155

148156
// copy old entries to new entries

0 commit comments

Comments
 (0)