what is the javascript internal data structure?

Question

Consider a basic js object:

var obj={x:1,y:'2'};

Is this stored internally as a hashtable or does js use a different mechanism for key value pairs? If they are hash tables does anyone know how they handle collisions?

• user40980: Its likely up to the various engine as to how the internals are represented. Beyond that, it doesn't appear to say in the ECMA definition.

Answer 1

"javascript internal" doesn't really mean anything, as far as I know, such thing isn't specified for Javascript.

For some Javascript engine or interpreter, the internal representation can be any number of things, whatever works for any given situation.

For long-lived objects of indeterminate lifetime, it's most likely a hash table, but also a list (or whatever) of property names in natural ("alphabetical") sorted order probably exists at least temporarily.

Arrays, as much as they exist in Javascript, probably also have a custom, optimized internal data structure, which may support faster indexed access than going through creating a hash table hash.

And then a JS engine doing JIT might for example see that the object is never used for anything, in which case that object can be nothing internally, the instance is just optimized away and never actually created.

Answer 2

Depends on the implementation.

From v8/src/objects.h (Chrome's V8):

// Inheritance hierarchy:
// - MaybeObject (an object or a failure)
// - Failure (immediate for marking failed operation)
// - Object
// - Smi (immediate small integer)
// - HeapObject (superclass for everything allocated in the heap)
// - JSReceiver (suitable for property access)
// - JSObject
// - JSArray
// - JSArrayBuffer
// - JSArrayBufferView
// - JSTypedArray
// - JSDataView
// - JSSet
// - JSMap
// - JSSetIterator
// - JSMapIterator
// - JSWeakCollection
// - JSWeakMap
// - JSWeakSet
// - JSRegExp
// - JSFunction
// - JSGeneratorObject
// - JSModule
// - GlobalObject
// - JSGlobalObject
// - JSBuiltinsObject
// - JSGlobalProxy
// - JSValue
// - JSDate
// - JSMessageObject
// - JSProxy
// - JSFunctionProxy
// - FixedArrayBase
// - ByteArray
// - FixedArray
// - DescriptorArray
// - HashTable
// - Dictionary
// - StringTable
// - CompilationCacheTable
// - CodeCacheHashTable
// - MapCache
// - OrderedHashTable
// - OrderedHashSet
// - OrderedHashMap
// - Context
// - JSFunctionResultCache
// - ScopeInfo
// - TransitionArray
// - FixedDoubleArray
// - ExternalArray
// - ExternalUint8ClampedArray
// - ExternalInt8Array
// - ExternalUint8Array
// - ExternalInt16Array
// - ExternalUint16Array
// - ExternalInt32Array
// - ExternalUint32Array
// - ExternalFloat32Array
// - Name
// - String
// - SeqString
// - SeqOneByteString
// - SeqTwoByteString
// - SlicedString
// - ConsString
// - ExternalString
// - ExternalAsciiString
// - ExternalTwoByteString
// - InternalizedString
// - SeqInternalizedString
// - SeqOneByteInternalizedString
// - SeqTwoByteInternalizedString
// - ConsInternalizedString
// - ExternalInternalizedString
// - ExternalAsciiInternalizedString
// - ExternalTwoByteInternalizedString
// - Symbol
// - HeapNumber
// - Cell
// - PropertyCell
// - Code
// - Map
// - Oddball
// - Foreign
// - SharedFunctionInfo
// - Struct
// - Box
// - DeclaredAccessorDescriptor
// - AccessorInfo
// - DeclaredAccessorInfo
// - ExecutableAccessorInfo
// - AccessorPair
// - AccessCheckInfo
// - InterceptorInfo
// - CallHandlerInfo
// - TemplateInfo
// - FunctionTemplateInfo
// - ObjectTemplateInfo
// - Script
// - SignatureInfo
// - TypeSwitchInfo
// - DebugInfo
// - BreakPointInfo
// - CodeCache
//
// Formats of Object*:
// Smi: [31 bit signed int] 0
// HeapObject: [32 bit direct pointer] (4 byte aligned) | 01
// Failure: [30 bit signed int] 11

Can't say for certain but I'd imagine it's a JSMap considering a JSReceiver is "suitable for property access".

From mozjs-24.2.0/js/src/jsobj.h (Firefox's SpiderMonkey):

/*
 * JS object definitions.
 *
 * A JS object consists of a possibly-shared object descriptor containing
 * ordered property names, called the map; and a dense vector of property
 * values, called slots. The map/slot pointer pair is GC'ed, while the map
 * is reference counted and the slot vector is malloc'ed.
 */

Looks like a map again.

If you're really curious you might want to check out the source yourself.

Answer 3

The ECMAScript specification does not prescribe any particular implementation strategy. And why would it? Having different engines compete for performance using different implementation strategies is a Good ThingTM.