runtime/ArrayConventions.h

   1 /*
   2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
   3  *  Copyright (C) 2003, 2007, 2008, 2009, 2012 Apple Inc. All rights reserved.
   4  *
   5  *  This library is free software; you can redistribute it and/or
   6  *  modify it under the terms of the GNU Lesser General Public
   7  *  License as published by the Free Software Foundation; either
   8  *  version 2 of the License, or (at your option) any later version.
   9  *
  10  *  This library is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  *  Lesser General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU Lesser General Public
  16  *  License along with this library; if not, write to the Free Software
  17  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  18  *
  19  */
  20
  21 #ifndef ArrayConventions_h
  22 #define ArrayConventions_h
  23
  24 #include "IndexingHeader.h"
  25 #include "WriteBarrier.h"
  26
  27 namespace JSC {
  28
  29 // Overview of JSArray
  30 //
  31 // Properties of JSArray objects may be stored in one of three locations:
  32 //   * The regular JSObject property map.
  33 //   * A storage vector.
  34 //   * A sparse map of array entries.
  35 //
  36 // Properties with non-numeric identifiers, with identifiers that are not representable
  37 // as an unsigned integer, or where the value is greater than  MAX_ARRAY_INDEX
  38 // (specifically, this is only one property - the value 0xFFFFFFFFU as an unsigned 32-bit
  39 // integer) are not considered array indices and will be stored in the JSObject property map.
  40 //
  41 // All properties with a numeric identifer, representable as an unsigned integer i,
  42 // where (i <= MAX_ARRAY_INDEX), are an array index and will be stored in either the
  43 // storage vector or the sparse map. An array index i will be handled in the following
  44 // fashion:
  45 //
  46 //   * Where (i < MIN_SPARSE_ARRAY_INDEX) the value will be stored in the storage vector,
  47 //     unless the array is in SparseMode in which case all properties go into the map.
  48 //   * Where (MIN_SPARSE_ARRAY_INDEX <= i <= MAX_STORAGE_VECTOR_INDEX) the value will either
  49 //     be stored in the storage vector or in the sparse array, depending on the density of
  50 //     data that would be stored in the vector (a vector being used where at least
  51 //     (1 / minDensityMultiplier) of the entries would be populated).
  52 //   * Where (MAX_STORAGE_VECTOR_INDEX < i <= MAX_ARRAY_INDEX) the value will always be stored
  53 //     in the sparse array.
  54
  55 // Define the maximum storage vector length to be 2^32 / sizeof(JSValue) / 2 to ensure that
  56 // there is no risk of overflow.
  57 #define MAX_STORAGE_VECTOR_LENGTH (static_cast<unsigned>(IndexingHeader::maximumLength))
  58
  59 // These values have to be macros to be used in max() and min() without introducing
  60 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
  61 #define MIN_SPARSE_ARRAY_INDEX 100000U
  62 #define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
  63 // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
  64 #define MAX_ARRAY_INDEX 0xFFFFFFFEU
  65
  66 // The value BASE_VECTOR_LEN is the maximum number of vector elements we'll allocate
  67 // for an array that was created with a sepcified length (e.g. a = new Array(123))
  68 #define BASE_VECTOR_LEN 4U
  69
  70 // The upper bound to the size we'll grow a zero length array when the first element
  71 // is added.
  72 #define FIRST_VECTOR_GROW 4U
  73
  74 #define MIN_BEYOND_LENGTH_SPARSE_INDEX 1000
  75
  76 // Our policy for when to use a vector and when to use a sparse map.
  77 // For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector.
  78 // When indices greater than MIN_SPARSE_ARRAY_INDEX are involved, we use a vector
  79 // as long as it is 1/8 full. If more sparse than that, we use a map.
  80 static const unsigned minDensityMultiplier = 8;
  81
  82 inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
  83 {
  84     return length / minDensityMultiplier <= numValues;
  85 }
  86
  87 inline bool indexIsSufficientlyBeyondLengthForSparseMap(unsigned i, unsigned length)
  88 {
  89     return i >= MIN_BEYOND_LENGTH_SPARSE_INDEX && i > length;
  90 }
  91
  92 inline IndexingHeader indexingHeaderForArray(unsigned length, unsigned vectorLength)
  93 {
  94     IndexingHeader result;
  95     result.setPublicLength(length);
  96     result.setVectorLength(vectorLength);
  97     return result;
  98 }
  99
 100 inline IndexingHeader baseIndexingHeaderForArray(unsigned length)
 101 {
 102     return indexingHeaderForArray(length, BASE_VECTOR_LEN);
 103 }
 104
 105 } // namespace JSC
 106
 107 #endif // ArrayConventions_h
 108