[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-commits
Subject: KDE/kdelibs/kjs
From: Maks Orlovich <maksim () kde ! org>
Date: 2010-04-30 19:43:54
Message-ID: 20100430194354.64C31AC8AA () svn ! kde ! org
[Download RAW message or body]
SVN commit 1121202 by orlovich:
Adopt JSC r34204 (+ a performance tweak from earlier one), which
fixes some spare -> dense compaction scenarios dropping array
elements.
M +35 -42 array_instance.cpp
--- trunk/KDE/kdelibs/kjs/array_instance.cpp #1121201:1121202
@@ -2,7 +2,7 @@
/*
* This file is part of the KDE libraries
* Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
- * Copyright (C) 2003, 2007 Apple Inc. All rights reserved.
+ * Copyright (C) 2003, 2007, 2008 Apple Inc. All rights reserved.
* Copyright (C) 2003 Peter Kelly (pmk@post.com)
* Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
*
@@ -213,19 +213,19 @@
void ArrayInstance::put(ExecState* exec, unsigned i, JSValue* value, int attributes)
{
+ unsigned length = m_length;
+
+ if (i >= length) {
if (i > maxArrayIndex) {
put(exec, Identifier::from(i), value, attributes);
return;
}
-
- ArrayStorage* storage = m_storage;
-
- unsigned length = m_length;
- if (i >= length) {
length = i + 1;
m_length = length;
}
+ ArrayStorage* storage = m_storage;
+
if (i < m_vectorLength) {
JSValue*& valueSlot = storage->m_vector[i];
storage->m_numValuesInVector += !valueSlot;
@@ -233,24 +233,9 @@
return;
}
- if (i < sparseArrayCutoff) {
- increaseVectorLength(i + 1);
- storage = m_storage;
- ++storage->m_numValuesInVector;
- storage->m_vector[i] = value;
- return;
- }
-
SparseArrayValueMap* map = storage->m_sparseValueMap;
- if (!map || map->isEmpty()) {
- // i is after the vector here, see if it makes sense to expand the vector to \
include it.
- if (isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
- increaseVectorLength(i + 1);
- storage = m_storage;
- ++storage->m_numValuesInVector;
- storage->m_vector[i] = value;
- return;
- }
+ if (i >= sparseArrayCutoff) {
+ // If the index is high, go to the map unless we're pretty dense.
if (!map) {
map = new SparseArrayValueMap;
storage->m_sparseValueMap = map;
@@ -262,24 +247,33 @@
if (!m_vectorLength)
increaseVectorLength(1);
}
- map->add(i, value);
+
+ map->set(i, value);
return;
}
- // See if we want to expand it to include i.
- // ### actually, this does not honor the stated heuristic, since there may be \
values
- // between vectorLength and i inside the map. I am not sure if checking that
- // would be wise, however -- Maks
- unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
- if (!isDenseEnoughForVector(i + 1, newNumValuesInVector)) {
- map->add(i, value);
+ // note: an invariant here is that indeces < sparseArrayCutoff
+ // are always inside the vector portion.
+
+ // lowish indeces or high density -> we have decided that we'll put the new item \
into the vector. + // Fast case is when there is no sparse map, so we can increase \
the vector size without moving values from the sparse map. + if (!map || \
map->isEmpty()) { + increaseVectorLength(i + 1);
+ storage = m_storage;
+ ++storage->m_numValuesInVector;
+ storage->m_vector[i] = value;
return;
}
- // Since we're expanding the vector, we want to copy over things from the map
+ // Decide just how large we want to make the vector to be.
+ unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
unsigned newVectorLength = increasedVectorLength(i + 1);
- for (unsigned j = m_vectorLength; j < newVectorLength; ++j)
+
+ // First, count how much stuff we are guaranteed to move over, now
+ // that we've decided to at least include i in the vector.
+ for (unsigned j = max(m_vectorLength, sparseArrayCutoff); j < newVectorLength; \
++j) newNumValuesInVector += map->contains(j);
+ if (i >= sparseArrayCutoff)
newNumValuesInVector -= map->contains(i);
// Continue increasing the vector portion as long as the things in the map are \
dense enough @@ -287,7 +281,7 @@
unsigned proposedNewNumValuesInVector = newNumValuesInVector;
while (true) {
unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength \
+ 1);
- for (unsigned j = newVectorLength; j < proposedNewVectorLength; ++j)
+ for (unsigned j = max(newVectorLength, sparseArrayCutoff); j < \
proposedNewVectorLength; ++j) proposedNewNumValuesInVector += map->contains(j);
if (!isDenseEnoughForVector(proposedNewVectorLength, \
proposedNewNumValuesInVector)) break;
@@ -305,19 +299,15 @@
if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
for (unsigned j = vectorLength; j < newVectorLength; ++j)
storage->m_vector[j] = 0;
+ if (i > sparseArrayCutoff)
map->remove(i);
} else {
// Move over things from the map to the new array portion
- for (unsigned j = vectorLength; j < newVectorLength; ++j) {
- SparseArrayValueMap::iterator it = map->find(j);
- if (it == map->end())
+ for (unsigned j = vectorLength; j < max(vectorLength, sparseArrayCutoff); \
++j) storage->m_vector[j] = 0;
- else {
- storage->m_vector[j] = it->second;
- map->remove(it);
+ for (unsigned j = max(vectorLength, sparseArrayCutoff); j < newVectorLength; \
++j) + storage->m_vector[j] = map->take(j);
}
- }
- }
storage->m_vector[i] = value;
@@ -390,6 +380,9 @@
void ArrayInstance::increaseVectorLength(unsigned newLength)
{
+ // This function leaves the array in an internally inconsistent state, because \
it does not move any values from sparse value map + // to the vector. Callers have \
to account for that, because they can do it more efficiently. +
ArrayStorage* storage = m_storage;
unsigned vectorLength = m_vectorLength;
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic