[[ 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.
livecode · runrevmark · Nov 7, 2018 · Nov 7, 2018 · Nov 7, 2018 · Nov 7, 2018
commit 797437581bd39570790cbfa73cdcc3a34fc67435
diff --git a/engine/src/exec.cpp b/engine/src/exec.cpp
@@ -365,10 +365,36 @@ bool MCExecContext::ConvertToData(MCValueRef p_value, MCDataRef& r_data)

 bool MCExecContext::ConvertToName(MCValueRef p_value, MCNameRef& r_name)
 {
-    if (MCValueGetTypeCode(p_value) == kMCValueTypeCodeName)
+
+    switch(MCValueGetTypeCode(p_value))
    {
-        r_name = MCValueRetain((MCNameRef)p_value);
-        return true;
+        case kMCValueTypeCodeName:
+        {
+            r_name = MCValueRetain((MCNameRef)p_value);
+            return true;
+        }
+
+        case kMCValueTypeCodeString:
+        {
+            return MCNameCreate((MCStringRef)p_value,
+                                r_name);
+        }
+
+        case kMCValueTypeCodeNumber:
+        {
+            index_t t_index;
+            if (MCNumberStrictFetchAsIndex((MCNumberRef)p_value,
+                                           t_index))
+            {
+                return MCNameCreateWithIndex(t_index,
+                                             r_name);
+            }
+            else
+                break;
+        }
+
+        default:
+            break;
    }

    MCAutoStringRef t_string;

diff --git a/libfoundation/include/foundation.h b/libfoundation/include/foundation.h
@@ -2049,6 +2049,9 @@ MC_DLLEXPORT integer_t MCNumberFetchAsInteger(MCNumberRef number);
 MC_DLLEXPORT uinteger_t MCNumberFetchAsUnsignedInteger(MCNumberRef number);
 MC_DLLEXPORT real64_t MCNumberFetchAsReal(MCNumberRef number);

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

 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);
 MC_DLLEXPORT bool MCNameCreateWithChars(const unichar_t *chars, uindex_t count, MCNameRef& r_name);
 // Create a name using native chars.
 MC_DLLEXPORT bool MCNameCreateWithNativeChars(const char_t *chars, uindex_t count, MCNameRef& r_name);
-
+// Create a name using an index
+MC_DLLEXPORT bool MCNameCreateWithIndex(index_t p_index, MCNameRef& r_name);
+
 // Create a name using the given string, releasing the original.
 MC_DLLEXPORT bool MCNameCreateAndRelease(MCStringRef string, MCNameRef& r_name);

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

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

diff --git a/libfoundation/src/foundation-array.cpp b/libfoundation/src/foundation-array.cpp
@@ -569,44 +569,48 @@ bool MCArrayRemoveValueOnPath(MCArrayRef array,
 MC_DLLEXPORT_DEF
 bool MCArrayFetchValueAtIndex(MCArrayRef self, index_t p_index, MCValueRef& r_value)
 {
-	__MCAssertIsArray(self);
-
-	char t_index_str[16];
-	sprintf(t_index_str, "%d", p_index);
-
-	MCNewAutoNameRef t_key;
-	if (!MCNameCreateWithNativeChars((const char_t *)t_index_str, strlen(t_index_str), &t_key))
-		return false;
-
-	return MCArrayFetchValue(self, true, *t_key, r_value);
+    __MCAssertIsArray(self);
+
+    MCNameRef t_key =
+            MCNameLookupIndex(p_index);
+
+    if (t_key == nil)
+    {
+        return false;
+    }
+
+    return MCArrayFetchValue(self, true, t_key, r_value);
 }

 MC_DLLEXPORT_DEF
 bool MCArrayStoreValueAtIndex(MCArrayRef self, index_t p_index, MCValueRef p_value)
 {
-	__MCAssertIsArray(self);
-
-	char t_index_str[16];
-	sprintf(t_index_str, "%d", p_index);
-
-	MCNewAutoNameRef t_key;
-	if (!MCNameCreateWithNativeChars((const char_t *)t_index_str, strlen(t_index_str), &t_key))
-		return false;
-
-	return MCArrayStoreValue(self, true, *t_key, p_value);
+    __MCAssertIsArray(self);
+    
+    MCNewAutoNameRef t_key;
+    if (!MCNameCreateWithIndex(p_index,
+                               &t_key))
+    {
+        return false;
+    }
+    
+    return MCArrayStoreValue(self, true, *t_key, p_value);
 }

 bool
 MCArrayRemoveValueAtIndex(MCArrayRef self, index_t p_index)
 {
-	char t_index_str[16];
-	sprintf(t_index_str, "%d", p_index);
-	MCNewAutoNameRef t_key;
-	if (!MCNameCreateWithNativeChars((const char_t *)t_index_str,
-									 strlen(t_index_str),
-									 &t_key))
-		return false;
-	return MCArrayRemoveValue(self, true, *t_key);
+    __MCAssertIsArray(self);
+
+    MCNameRef t_key =
+            MCNameLookupIndex(p_index);
+
+    if (t_key == nil)
+    {
+        return true;
+    }
+
+    return MCArrayRemoveValue(self, true, t_key);
 }

 ////////////////////////////////////////////////////////////////////////////////

diff --git a/libfoundation/src/foundation-name.cpp b/libfoundation/src/foundation-name.cpp
@@ -18,6 +18,8 @@ along with LiveCode.  If not see <http://www.gnu.org/licenses/>.  */

 #include "foundation-private.h"

+#include "foundation-string-hash.h"
+
 ////////////////////////////////////////////////////////////////////////////////

 MC_DLLEXPORT_DEF MCNameRef kMCEmptyName;
@@ -45,6 +47,102 @@ static inline void __MCNameSetHash(__MCName* p_name, hash_t p_hash)
    p_name->flags = (p_name->flags & kMCValueFlagsTypeCodeMask) | (p_hash & kMCValueFlagsNameHashMask);
 }

+static void __MCNameIndexToNativeChars(index_t p_value, char_t r_chars[16], uindex_t& r_char_count)
+{
+    static const char kDigits[201] =
+        "0001020304050607080910111213141516171819"
+        "2021222324252627282930313233343536373839"
+        "4041424344454647484950515253545556575859"
+        "6061626364656667686970717273747576777879"
+        "8081828384858687888990919293949596979899";
+
+    r_char_count = 0;
+
+    uindex_t t_value;
+    if (p_value < 0)
+    {
+        r_chars[r_char_count++] = '-';
+        p_value = -p_value;
+    }
+
+    t_value = p_value;
+
+    uint32_t t_length = 1;
+    for (;;) {
+        if (t_value < 10) break;
+        if (t_value < 100) { t_length += 1; break; }
+        if (t_value < 1000) { t_length += 2; break; }
+        if (t_value < 10000) { t_length += 3; break; }
+        t_value /= 10000U;
+        t_length += 4;
+    }
+
+    t_value = p_value;
+
+    r_char_count += t_length;
+
+    uindex_t t_next =
+        r_char_count - 1;
+
+    while(t_value >= 100)
+    {
+        index_t t_offset =
+                    (t_value % 100) * 2;
+
+        t_value /= 100;
+
+        r_chars[t_next] = kDigits[t_offset + 1];
+        r_chars[t_next - 1] = kDigits[t_offset];
+
+        t_next -= 2;
+    }
+
+    if (t_value < 10)
+    {
+        r_chars[t_next] = '0' + t_value;
+    }
+    else
+    {
+        index_t t_offset =
+                    t_value * 2;
+
+        r_chars[t_next] = kDigits[t_offset + 1];
+        r_chars[t_next - 1] = kDigits[t_offset];
+    }
+}
+
+static hash_t __MCNameIndexHash(const char_t *p_chars, uindex_t p_char_count)
+{
+    MCHashCharsContext t_hash;
+    switch(p_char_count)
+    {
+    case 11:
+        t_hash.consume(*p_chars++);
+    case 10:
+        t_hash.consume(*p_chars++);
+    case 9:
+        t_hash.consume(*p_chars++);
+    case 8:
+        t_hash.consume(*p_chars++);
+    case 7:
+        t_hash.consume(*p_chars++);
+    case 6:
+        t_hash.consume(*p_chars++);
+    case 5:
+        t_hash.consume(*p_chars++);
+    case 4:
+        t_hash.consume(*p_chars++);
+    case 3:
+        t_hash.consume(*p_chars++);
+    case 2:
+        t_hash.consume(*p_chars++);
+    case 1:
+        t_hash.consume(*p_chars++);
+        break;
+    }
+    return t_hash;
+}
+
 ////////////////////////////////////////////////////////////////////////////////

 MC_DLLEXPORT_DEF
@@ -178,6 +276,92 @@ bool MCNameCreate(MCStringRef p_string, MCNameRef& r_name)
 	return t_success;
 }

+MC_DLLEXPORT_DEF
+bool MCNameCreateWithIndex(index_t p_index, MCNameRef& r_name)
+{
+    char_t t_chars[11];
+    uindex_t t_char_count;
+    __MCNameIndexToNativeChars(p_index, t_chars, t_char_count);
+
+    // Compute the hash of the characters, up to case.
+    hash_t t_hash;
+    t_hash = __MCNameIndexHash(t_chars, t_char_count);
+
+    // Reduce the hash to the size we store
+    t_hash &= kMCValueFlagsNameHashMask;
+
+    // Calculate the index of the chain in the name table where this might be
+    // found. The capacity is always a power-of-two, so its just a mask op.
+    uindex_t t_index;
+    t_index = t_hash & (s_name_table_capacity - 1);
+
+    // Search for the first representation of the would-be name's equivalence
+    // class.
+    __MCName *t_key_name;
+    t_key_name = s_name_table[t_index];
+    while(t_key_name != nil)
+    {
+        // If the string matches, then we are done - notice we compare the
+        // full hash first.
+        if (t_hash == __MCNameGetHash(t_key_name) &&
+            t_key_name -> key == t_key_name &&
+            MCStringIsEqualToNativeChars(t_key_name -> string, t_chars, t_char_count, kMCStringOptionCompareExact))
+        {
+            t_key_name -> references += 1;
+            r_name = t_key_name;
+            return true;
+        }
+
+        // Next name must be the next one.
+        t_key_name = t_key_name -> next;
+    }
+
+    // We haven't found an exact match, so we create a new name...
+    bool t_success;
+    t_success = true;
+
+    // Allocate a name record.
+    __MCName *t_name;
+    if (t_success)
+        t_success = __MCValueCreate(kMCValueTypeCodeName, t_name);
+
+    // Copy the string (as immutable).
+    if (t_success)
+        t_success = MCStringCreateWithNativeChars(t_chars, t_char_count, t_name -> string);
+
+    // Now add the name to the table and fill in the rest of the fields.
+    if (t_success)
+    {
+        // To keep hashin efficient, we (try to) double the size of the
+        // table each time occupancy reaches capacity.
+        if (s_name_table_occupancy == s_name_table_capacity)
+        {
+            __MCNameGrowTable();
+            t_index = t_hash & (s_name_table_capacity - 1);
+        }
+
+        // Increase occupancy.
+        s_name_table_occupancy += 1;
+
+        t_name -> next = s_name_table[t_index];
+        t_name -> key = t_name;
+        s_name_table[t_index] = t_name;
+
+        // Record the hash (speeds up searching and such).
+        __MCNameSetHash(t_name, t_hash);
+
+        // Return the new name.
+        r_name = t_name;
+    }
+    else
+    {
+        MCValueRelease(t_name -> string);
+        MCMemoryDelete(t_name);
+    }
+
+    return t_success;
+}
+
 MC_DLLEXPORT_DEF
 bool MCNameCreateWithNativeChars(const char_t *p_chars, uindex_t p_count, MCNameRef& r_name)
 {
@@ -250,6 +434,45 @@ MCNameRef MCNameLookupCaseless(MCStringRef p_string)
 	return t_key_name;
 }

+MC_DLLEXPORT_DEF
+MCNameRef MCNameLookupIndex(index_t p_index)
+{
+    char_t t_chars[11];
+    uindex_t t_char_count;
+    __MCNameIndexToNativeChars(p_index, t_chars, t_char_count);
+
+    // Compute the hash of the characters, up to case.
+    hash_t t_hash;
+    t_hash = __MCNameIndexHash(t_chars, t_char_count);
+
+    // Reduce the hash to the size we store
+    t_hash &= kMCValueFlagsNameHashMask;
+
+    // Calculate the index of the chain in the name table where this name might
+    // be found. The capacity is always a power-of-two, so its just a mask op.
+    uindex_t t_index;
+    t_index = t_hash & (s_name_table_capacity - 1);
+
+    // Search for the first representative of the would-be name's equivalence class.
+    __MCName *t_key_name;
+    t_key_name = s_name_table[t_index];
+    while(t_key_name != nil)
+    {
+        // If the string matches, then we are done - notice we compare the full
+        // hash first. As an index as a string consists of folded chars, we can
+        // use exact comparison.
+        if (t_hash == __MCNameGetHash(t_key_name) &&
+            t_key_name->key == t_key_name &&
+            MCStringIsEqualToNativeChars(t_key_name -> string, t_chars, t_char_count, kMCStringOptionCompareExact))
+            break;
+
+        // Next name must be the next one
+        t_key_name = t_key_name -> next;
+    }
+
+    return t_key_name;
+}
+
 MC_DLLEXPORT_DEF
 uintptr_t MCNameGetCaselessSearchKey(MCNameRef self)
 {