Skip to content
This repository was archived by the owner on Aug 31, 2021. It is now read-only.

Commit d40bc41

Browse files
runrevmarkrunrevmark
committed
[[ Perf ]] Implement optimized 'index' names
This patch introduces the concept of an 'index' MCNameRef, one which is generated from an index_t value. Index names have optimized code paths for conversion of the index to a string, hashing and insertion into the name table - all taking advantage of the unique properties integer strings have.
1 parent 33ee0b4 commit d40bc41

File tree

5 files changed

+316
-32
lines changed

5 files changed

+316
-32
lines changed

‎engine/src/exec.cpp‎

Lines changed: 29 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -365,10 +365,36 @@ bool MCExecContext::ConvertToData(MCValueRef p_value, MCDataRef& r_data)
365365

366366
bool MCExecContext::ConvertToName(MCValueRef p_value, MCNameRef& r_name)
367367
{
368-
if (MCValueGetTypeCode(p_value) == kMCValueTypeCodeName)
368+
369+
switch(MCValueGetTypeCode(p_value))
369370
{
370-
r_name = MCValueRetain((MCNameRef)p_value);
371-
return true;
371+
case kMCValueTypeCodeName:
372+
{
373+
r_name = MCValueRetain((MCNameRef)p_value);
374+
return true;
375+
}
376+
377+
case kMCValueTypeCodeString:
378+
{
379+
return MCNameCreate((MCStringRef)p_value,
380+
r_name);
381+
}
382+
383+
case kMCValueTypeCodeNumber:
384+
{
385+
index_t t_index;
386+
if (MCNumberStrictFetchAsIndex((MCNumberRef)p_value,
387+
t_index))
388+
{
389+
return MCNameCreateWithIndex(t_index,
390+
r_name);
391+
}
392+
else
393+
break;
394+
}
395+
396+
default:
397+
break;
372398
}
373399

374400
MCAutoStringRef t_string;

‎libfoundation/include/foundation.h‎

Lines changed: 8 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2049,6 +2049,9 @@ MC_DLLEXPORT integer_t MCNumberFetchAsInteger(MCNumberRef number);
20492049
MC_DLLEXPORT uinteger_t MCNumberFetchAsUnsignedInteger(MCNumberRef number);
20502050
MC_DLLEXPORT real64_t MCNumberFetchAsReal(MCNumberRef number);
20512051

2052+
MC_DLLEXPORT bool MCNumberStrictFetchAsIndex(MCNumberRef number,
2053+
index_t& r_index);
2054+
20522055
MC_DLLEXPORT bool MCNumberParseOffsetPartial(MCStringRef p_string, uindex_t offset, uindex_t &r_chars_used, MCNumberRef &r_number);
20532056

20542057
MC_DLLEXPORT bool MCNumberParseOffset(MCStringRef p_string, uindex_t offset, uindex_t char_count, MCNumberRef &r_number);
@@ -2775,12 +2778,16 @@ MC_DLLEXPORT bool MCNameCreate(MCStringRef string, MCNameRef& r_name);
27752778
MC_DLLEXPORT bool MCNameCreateWithChars(const unichar_t *chars, uindex_t count, MCNameRef& r_name);
27762779
// Create a name using native chars.
27772780
MC_DLLEXPORT bool MCNameCreateWithNativeChars(const char_t *chars, uindex_t count, MCNameRef& r_name);
2778-
2781+
// Create a name using an index
2782+
MC_DLLEXPORT bool MCNameCreateWithIndex(index_t p_index, MCNameRef& r_name);
2783+
27792784
// Create a name using the given string, releasing the original.
27802785
MC_DLLEXPORT bool MCNameCreateAndRelease(MCStringRef string, MCNameRef& r_name);
27812786

27822787
// Looks for an existing name matching the given string.
27832788
MC_DLLEXPORT MCNameRef MCNameLookupCaseless(MCStringRef string);
2789+
// Looks for an existing name matching the given index.
2790+
MC_DLLEXPORT MCNameRef MCNameLookupIndex(index_t p_index);
27842791

27852792
// Returns a unsigned integer which can be used to order a table for a binary
27862793
// search.

‎libfoundation/src/foundation-array.cpp‎

Lines changed: 32 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -569,44 +569,48 @@ bool MCArrayRemoveValueOnPath(MCArrayRef array,
569569
MC_DLLEXPORT_DEF
570570
bool MCArrayFetchValueAtIndex(MCArrayRef self, index_t p_index, MCValueRef& r_value)
571571
{
572-
__MCAssertIsArray(self);
573-
574-
char t_index_str[16];
575-
sprintf(t_index_str, "%d", p_index);
576-
577-
MCNewAutoNameRef t_key;
578-
if (!MCNameCreateWithNativeChars((const char_t *)t_index_str, strlen(t_index_str), &t_key))
579-
return false;
580-
581-
return MCArrayFetchValue(self, true, *t_key, r_value);
572+
__MCAssertIsArray(self);
573+
574+
MCNameRef t_key =
575+
MCNameLookupIndex(p_index);
576+
577+
if (t_key == nil)
578+
{
579+
return false;
580+
}
581+
582+
return MCArrayFetchValue(self, true, t_key, r_value);
582583
}
583584

584585
MC_DLLEXPORT_DEF
585586
bool MCArrayStoreValueAtIndex(MCArrayRef self, index_t p_index, MCValueRef p_value)
586587
{
587-
__MCAssertIsArray(self);
588-
589-
char t_index_str[16];
590-
sprintf(t_index_str, "%d", p_index);
591-
592-
MCNewAutoNameRef t_key;
593-
if (!MCNameCreateWithNativeChars((const char_t *)t_index_str, strlen(t_index_str), &t_key))
594-
return false;
595-
596-
return MCArrayStoreValue(self, true, *t_key, p_value);
588+
__MCAssertIsArray(self);
589+
590+
MCNewAutoNameRef t_key;
591+
if (!MCNameCreateWithIndex(p_index,
592+
&t_key))
593+
{
594+
return false;
595+
}
596+
597+
return MCArrayStoreValue(self, true, *t_key, p_value);
597598
}
598599

599600
bool
600601
MCArrayRemoveValueAtIndex(MCArrayRef self, index_t p_index)
601602
{
602-
char t_index_str[16];
603-
sprintf(t_index_str, "%d", p_index);
604-
MCNewAutoNameRef t_key;
605-
if (!MCNameCreateWithNativeChars((const char_t *)t_index_str,
606-
strlen(t_index_str),
607-
&t_key))
608-
return false;
609-
return MCArrayRemoveValue(self, true, *t_key);
603+
__MCAssertIsArray(self);
604+
605+
MCNameRef t_key =
606+
MCNameLookupIndex(p_index);
607+
608+
if (t_key == nil)
609+
{
610+
return true;
611+
}
612+
613+
return MCArrayRemoveValue(self, true, t_key);
610614
}
611615

612616
////////////////////////////////////////////////////////////////////////////////

‎libfoundation/src/foundation-name.cpp‎

Lines changed: 224 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,8 @@ along with LiveCode. If not see <http://www.gnu.org/licenses/>. */
1818

1919
#include "foundation-private.h"
2020

21+
#include "foundation-string-hash.h"
22+
2123
////////////////////////////////////////////////////////////////////////////////
2224

2325
MC_DLLEXPORT_DEF MCNameRef kMCEmptyName;
@@ -114,6 +116,104 @@ static inline void __MCNameSetNext(__MCName* p_name, __MCName* p_next)
114116

115117
////////////////////////////////////////////////////////////////////////////////
116118

119+
static void __MCNameIndexToNativeChars(index_t p_value, char_t r_chars[16], uindex_t& r_char_count)
120+
{
121+
static const char kDigits[201] =
122+
"0001020304050607080910111213141516171819"
123+
"2021222324252627282930313233343536373839"
124+
"4041424344454647484950515253545556575859"
125+
"6061626364656667686970717273747576777879"
126+
"8081828384858687888990919293949596979899";
127+
128+
r_char_count = 0;
129+
130+
uindex_t t_value;
131+
if (p_value < 0)
132+
{
133+
r_chars[r_char_count++] = '-';
134+
p_value = -p_value;
135+
}
136+
137+
t_value = p_value;
138+
139+
uint32_t t_length = 1;
140+
for (;;) {
141+
if (t_value < 10) break;
142+
if (t_value < 100) { t_length += 1; break; }
143+
if (t_value < 1000) { t_length += 2; break; }
144+
if (t_value < 10000) { t_length += 3; break; }
145+
t_value /= 10000U;
146+
t_length += 4;
147+
}
148+
149+
t_value = p_value;
150+
151+
r_char_count += t_length;
152+
153+
uindex_t t_next =
154+
r_char_count - 1;
155+
156+
while(t_value >= 100)
157+
{
158+
index_t t_offset =
159+
(t_value % 100) * 2;
160+
161+
t_value /= 100;
162+
163+
r_chars[t_next] = kDigits[t_offset + 1];
164+
r_chars[t_next - 1] = kDigits[t_offset];
165+
166+
t_next -= 2;
167+
}
168+
169+
if (t_value < 10)
170+
{
171+
r_chars[t_next] = '0' + t_value;
172+
}
173+
else
174+
{
175+
index_t t_offset =
176+
t_value * 2;
177+
178+
r_chars[t_next] = kDigits[t_offset + 1];
179+
r_chars[t_next - 1] = kDigits[t_offset];
180+
}
181+
}
182+
183+
static hash_t __MCNameIndexHash(const char_t *p_chars, uindex_t p_char_count)
184+
{
185+
MCHashCharsContext t_hash;
186+
switch(p_char_count)
187+
{
188+
case 11:
189+
t_hash.consume(*p_chars++);
190+
case 10:
191+
t_hash.consume(*p_chars++);
192+
case 9:
193+
t_hash.consume(*p_chars++);
194+
case 8:
195+
t_hash.consume(*p_chars++);
196+
case 7:
197+
t_hash.consume(*p_chars++);
198+
case 6:
199+
t_hash.consume(*p_chars++);
200+
case 5:
201+
t_hash.consume(*p_chars++);
202+
case 4:
203+
t_hash.consume(*p_chars++);
204+
case 3:
205+
t_hash.consume(*p_chars++);
206+
case 2:
207+
t_hash.consume(*p_chars++);
208+
case 1:
209+
t_hash.consume(*p_chars++);
210+
break;
211+
}
212+
return t_hash;
213+
}
214+
215+
////////////////////////////////////////////////////////////////////////////////
216+
117217
MC_DLLEXPORT_DEF
118218
MCNameRef MCNAME(const char *p_string)
119219
{
@@ -245,6 +345,92 @@ bool MCNameCreate(MCStringRef p_string, MCNameRef& r_name)
245345
return t_success;
246346
}
247347

348+
MC_DLLEXPORT_DEF
349+
bool MCNameCreateWithIndex(index_t p_index, MCNameRef& r_name)
350+
{
351+
char_t t_chars[11];
352+
uindex_t t_char_count;
353+
__MCNameIndexToNativeChars(p_index, t_chars, t_char_count);
354+
355+
// Compute the hash of the characters, up to case.
356+
hash_t t_hash;
357+
t_hash = __MCNameIndexHash(t_chars, t_char_count);
358+
359+
// Reduce the hash to the size we store
360+
t_hash = __MCNameReduceHash(t_hash);
361+
362+
// Calculate the index of the chain in the name table where this might be
363+
// found. The capacity is always a power-of-two, so its just a mask op.
364+
uindex_t t_index;
365+
t_index = t_hash & (s_name_table_capacity - 1);
366+
367+
// Search for the first representation of the would-be name's equivalence
368+
// class.
369+
__MCName *t_key_name;
370+
t_key_name = s_name_table[t_index];
371+
while(t_key_name != nil)
372+
{
373+
// If the string matches, then we are done - notice we compare the
374+
// full hash first.
375+
if (t_hash == __MCNameGetHash(t_key_name) &&
376+
__MCNameGetKey(t_key_name) == t_key_name &&
377+
MCStringIsEqualToNativeChars(t_key_name -> string, t_chars, t_char_count, kMCStringOptionCompareExact))
378+
{
379+
t_key_name -> references += 1;
380+
r_name = t_key_name;
381+
return true;
382+
}
383+
384+
// Next name must be the next one.
385+
t_key_name = __MCNameGetNext(t_key_name);
386+
}
387+
388+
// We haven't found an exact match, so we create a new name...
389+
bool t_success;
390+
t_success = true;
391+
392+
// Allocate a name record.
393+
__MCName *t_name;
394+
if (t_success)
395+
t_success = __MCValueCreate(kMCValueTypeCodeName, t_name);
396+
397+
// Copy the string (as immutable).
398+
if (t_success)
399+
t_success = MCStringCreateWithNativeChars(t_chars, t_char_count, t_name -> string);
400+
401+
// Now add the name to the table and fill in the rest of the fields.
402+
if (t_success)
403+
{
404+
// To keep hashin efficient, we (try to) double the size of the
405+
// table each time occupancy reaches capacity.
406+
if (s_name_table_occupancy == s_name_table_capacity)
407+
{
408+
__MCNameGrowTable();
409+
t_index = t_hash & (s_name_table_capacity - 1);
410+
}
411+
412+
// Increase occupancy.
413+
s_name_table_occupancy += 1;
414+
415+
__MCNameSetNext(t_name, s_name_table[t_index]);
416+
__MCNameSetKey(t_name, t_name);
417+
s_name_table[t_index] = t_name;
418+
419+
// Record the hash (speeds up searching and such).
420+
__MCNameSetHash(t_name, t_hash);
421+
422+
// Return the new name.
423+
r_name = t_name;
424+
}
425+
else
426+
{
427+
MCValueRelease(t_name -> string);
428+
MCMemoryDelete(t_name);
429+
}
430+
431+
return t_success;
432+
}
433+
248434
MC_DLLEXPORT_DEF
249435
bool MCNameCreateWithNativeChars(const char_t *p_chars, uindex_t p_count, MCNameRef& r_name)
250436
{
@@ -318,6 +504,44 @@ MCNameRef MCNameLookupCaseless(MCStringRef p_string)
318504
return t_key_name;
319505
}
320506

507+
MCNameRef MCNameLookupIndex(index_t p_index)
508+
{
509+
char_t t_chars[11];
510+
uindex_t t_char_count;
511+
__MCNameIndexToNativeChars(p_index, t_chars, t_char_count);
512+
513+
// Compute the hash of the characters, up to case.
514+
hash_t t_hash;
515+
t_hash = __MCNameIndexHash(t_chars, t_char_count);
516+
517+
// Reduce the hash to the size we store
518+
t_hash = __MCNameReduceHash(t_hash);
519+
520+
// Calculate the index of the chain in the name table where this name might
521+
// be found. The capacity is always a power-of-two, so its just a mask op.
522+
uindex_t t_index;
523+
t_index = t_hash & (s_name_table_capacity - 1);
524+
525+
// Search for the first representative of the would-be name's equivalence class.
526+
__MCName *t_key_name;
527+
t_key_name = s_name_table[t_index];
528+
while(t_key_name != nil)
529+
{
530+
// If the string matches, then we are done - notice we compare the full
531+
// hash first. As an index as a string consists of folded chars, we can
532+
// use exact comparison.
533+
if (t_hash == __MCNameGetHash(t_key_name) &&
534+
__MCNameGetKey(t_key_name) == t_key_name &&
535+
MCStringIsEqualToNativeChars(t_key_name -> string, t_chars, t_char_count, kMCStringOptionCompareExact))
536+
break;
537+
538+
// Next name must be the next one
539+
t_key_name = __MCNameGetNext(t_key_name);
540+
}
541+
542+
return t_key_name;
543+
}
544+
321545
MC_DLLEXPORT_DEF
322546
uintptr_t MCNameGetCaselessSearchKey(MCNameRef self)
323547
{

0 commit comments

Comments
 (0)