Backed out changeset 0d237b824f96 (bug 1017165) for causing bug 1037750 and bug 1037772.
authorRyan VanderMeulen <ryanvm@gmail.com>
Mon, 14 Jul 2014 15:40:24 -0400
changeset 214597 bf09d63db425d0be5d969b25714d79d767898bcd
parent 214596 fc0750213b619b5477b84c1c87d60abaf12ffffd
child 214637 2a22da38a185ad0421a438bd75d29c566836664a
push id3857
push userraliiev@mozilla.com
push dateTue, 02 Sep 2014 16:39:23 +0000
treeherdermozilla-beta@5638b907b505 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
bugs1017165, 1037750, 1037772
milestone33.0a1
backs out0d237b824f96c1d05466442f068ebc0a7b49fa78
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Backed out changeset 0d237b824f96 (bug 1017165) for causing bug 1037750 and bug 1037772.
js/src/gc/GCRuntime.h
js/src/gc/Heap.h
js/src/jsgc.cpp
js/src/jsgc.h
--- a/js/src/gc/GCRuntime.h
+++ b/js/src/gc/GCRuntime.h
@@ -695,22 +695,16 @@ class GCRuntime
 #endif
 
     /* Synchronize GC heap access between main thread and GCHelperState. */
     PRLock                *lock;
     mozilla::DebugOnly<PRThread *>   lockOwner;
 
     GCHelperState helperState;
 
-    /*
-     * During incremental sweeping, this field temporarily holds the arenas of
-     * the current AllocKind being swept in order of increasing free space.
-     */
-    SortedArenaList incrementalSweepList;
-
     ConservativeGCData conservativeGC;
 
     friend class js::GCHelperState;
     friend class js::gc::MarkingValidator;
     friend class js::gc::AutoTraceSession;
 };
 
 #ifdef JS_GC_ZEAL
--- a/js/src/gc/Heap.h
+++ b/js/src/gc/Heap.h
@@ -34,17 +34,16 @@ struct Runtime;
 namespace js {
 
 class FreeOp;
 
 namespace gc {
 
 struct Arena;
 class ArenaList;
-class SortedArenaList;
 struct ArenaHeader;
 struct Chunk;
 
 /*
  * This flag allows an allocation site to request a specific heap based upon the
  * estimated lifetime or lifetime requirements of objects allocated from that
  * site.
  */
@@ -593,17 +592,17 @@ struct Arena
 
     uintptr_t thingsEnd() {
         return address() + ArenaSize;
     }
 
     void setAsFullyUnused(AllocKind thingKind);
 
     template <typename T>
-    size_t finalize(FreeOp *fop, AllocKind thingKind, size_t thingSize);
+    bool finalize(FreeOp *fop, AllocKind thingKind, size_t thingSize);
 };
 
 static_assert(sizeof(Arena) == ArenaSize, "The hardcoded arena size must match the struct size.");
 
 inline size_t
 ArenaHeader::getThingSize() const
 {
     JS_ASSERT(allocated());
@@ -824,18 +823,17 @@ struct Chunk
 
     inline void addToAvailableList(JS::Zone *zone);
     inline void insertToAvailableList(Chunk **insertPoint);
     inline void removeFromAvailableList();
 
     ArenaHeader *allocateArena(JS::Zone *zone, AllocKind kind);
 
     void releaseArena(ArenaHeader *aheader);
-    void recycleArena(ArenaHeader *aheader, SortedArenaList &dest, AllocKind thingKind,
-                      size_t thingsPerArena);
+    void recycleArena(ArenaHeader *aheader, ArenaList &dest, AllocKind thingKind);
 
     static Chunk *allocate(JSRuntime *rt);
 
     void decommitAllArenas(JSRuntime *rt);
 
     /*
      * Assuming that the info.prevp points to the next field of the previous
      * chunk in a doubly-linked list, get that chunk.
--- a/js/src/jsgc.cpp
+++ b/js/src/jsgc.cpp
@@ -170,17 +170,16 @@
  * already, we continue until we have swept the current zone group. Following a
  * reset, a new non-incremental collection is started.
  */
 
 #include "jsgcinlines.h"
 
 #include "mozilla/ArrayUtils.h"
 #include "mozilla/DebugOnly.h"
-#include "mozilla/MacroForEach.h"
 #include "mozilla/MemoryReporting.h"
 #include "mozilla/Move.h"
 
 #include <string.h>     /* for memset used when DEBUG */
 #ifndef XP_WIN
 # include <unistd.h>
 #endif
 
@@ -251,24 +250,17 @@ const AllocKind gc::slotsToThingKind[] =
     /* 8 */  FINALIZE_OBJECT8,  FINALIZE_OBJECT12, FINALIZE_OBJECT12, FINALIZE_OBJECT12,
     /* 12 */ FINALIZE_OBJECT12, FINALIZE_OBJECT16, FINALIZE_OBJECT16, FINALIZE_OBJECT16,
     /* 16 */ FINALIZE_OBJECT16
 };
 
 static_assert(JS_ARRAY_LENGTH(slotsToThingKind) == SLOTS_TO_THING_KIND_LIMIT,
               "We have defined a slot count for each kind.");
 
-// Assert that SortedArenaList::MinThingSize is <= the real minimum thing size.
-#define CHECK_MIN_THING_SIZE_INNER(x_)                                         \
-    static_assert(x_ >= SortedArenaList::MinThingSize,                         \
-    #x_ " is less than SortedArenaList::MinThingSize!");
-#define CHECK_MIN_THING_SIZE(...) { __VA_ARGS__ }; /* Define the array. */     \
-    MOZ_FOR_EACH(CHECK_MIN_THING_SIZE_INNER, (), (__VA_ARGS__ UINT32_MAX))
-
-const uint32_t Arena::ThingSizes[] = CHECK_MIN_THING_SIZE(
+const uint32_t Arena::ThingSizes[] = {
     sizeof(JSObject),           /* FINALIZE_OBJECT0             */
     sizeof(JSObject),           /* FINALIZE_OBJECT0_BACKGROUND  */
     sizeof(JSObject_Slots2),    /* FINALIZE_OBJECT2             */
     sizeof(JSObject_Slots2),    /* FINALIZE_OBJECT2_BACKGROUND  */
     sizeof(JSObject_Slots4),    /* FINALIZE_OBJECT4             */
     sizeof(JSObject_Slots4),    /* FINALIZE_OBJECT4_BACKGROUND  */
     sizeof(JSObject_Slots8),    /* FINALIZE_OBJECT8             */
     sizeof(JSObject_Slots8),    /* FINALIZE_OBJECT8_BACKGROUND  */
@@ -281,20 +273,17 @@ const uint32_t Arena::ThingSizes[] = CHE
     sizeof(Shape),              /* FINALIZE_SHAPE               */
     sizeof(BaseShape),          /* FINALIZE_BASE_SHAPE          */
     sizeof(types::TypeObject),  /* FINALIZE_TYPE_OBJECT         */
     sizeof(JSFatInlineString),  /* FINALIZE_FAT_INLINE_STRING   */
     sizeof(JSString),           /* FINALIZE_STRING              */
     sizeof(JSExternalString),   /* FINALIZE_EXTERNAL_STRING     */
     sizeof(JS::Symbol),         /* FINALIZE_SYMBOL              */
     sizeof(jit::JitCode),       /* FINALIZE_JITCODE             */
-);
-
-#undef CHECK_MIN_THING_SIZE_INNER
-#undef CHECK_MIN_THING_SIZE
+};
 
 #define OFFSET(type) uint32_t(sizeof(ArenaHeader) + (ArenaSize - sizeof(ArenaHeader)) % sizeof(type))
 
 const uint32_t Arena::FirstThingOffsets[] = {
     OFFSET(JSObject),           /* FINALIZE_OBJECT0             */
     OFFSET(JSObject),           /* FINALIZE_OBJECT0_BACKGROUND  */
     OFFSET(JSObject_Slots2),    /* FINALIZE_OBJECT2             */
     OFFSET(JSObject_Slots2),    /* FINALIZE_OBJECT2_BACKGROUND  */
@@ -456,17 +445,17 @@ Arena::setAsFullyUnused(AllocKind thingK
 {
     FreeSpan fullSpan;
     size_t thingSize = Arena::thingSize(thingKind);
     fullSpan.initFinal(thingsStart(thingKind), thingsEnd() - thingSize, thingSize);
     aheader.setFirstFreeSpan(&fullSpan);
 }
 
 template<typename T>
-inline size_t
+inline bool
 Arena::finalize(FreeOp *fop, AllocKind thingKind, size_t thingSize)
 {
     /* Enforce requirements on size of T. */
     JS_ASSERT(thingSize % CellSize == 0);
     JS_ASSERT(thingSize <= 255);
 
     JS_ASSERT(aheader.allocated());
     JS_ASSERT(thingKind == aheader.getAllocKind());
@@ -502,17 +491,17 @@ Arena::finalize(FreeOp *fop, AllocKind t
             TraceTenuredFinalize(t);
         }
     }
 
     if (nmarked == 0) {
         // Do nothing. The caller will update the arena header appropriately.
         JS_ASSERT(newListTail == &newListHead);
         JS_EXTRA_POISON(data, JS_SWEPT_TENURED_PATTERN, sizeof(data));
-        return nmarked;
+        return true;
     }
 
     JS_ASSERT(firstThingOrSuccessorOfLastMarkedThing != firstThing);
     uintptr_t lastMarkedThing = firstThingOrSuccessorOfLastMarkedThing - thingSize;
     if (lastThing == lastMarkedThing) {
         // If the last thing was marked, we will have already set the bounds of
         // the final span, and we just need to terminate the list.
         newListTail->initAsEmpty();
@@ -523,88 +512,68 @@ Arena::finalize(FreeOp *fop, AllocKind t
 
 #ifdef DEBUG
     size_t nfree = 0;
     for (const FreeSpan *span = &newListHead; !span->isEmpty(); span = span->nextSpan())
         nfree += span->length(thingSize);
     JS_ASSERT(nfree + nmarked == thingsPerArena(thingSize));
 #endif
     aheader.setFirstFreeSpan(&newListHead);
-    return nmarked;
-}
-
-ArenaList 
-SortedArenaList::toArenaList()
-{
-    // Link the non-empty segment tails up to the non-empty segment heads.
-    size_t tailIndex = 0;
-    for (size_t headIndex = 1; headIndex <= thingsPerArena_; ++headIndex) {
-        if (headAt(headIndex)) {
-            segments[tailIndex].linkTo(headAt(headIndex));
-            tailIndex = headIndex;
-        }
-    }
-    // Point the tail of the final non-empty segment at null. Note that if the
-    // list is empty, this will just set segments[0].head to null, a noop.
-    segments[tailIndex].linkTo(nullptr);
-    // Return an ArenaList representing the flattened list.
-    return ArenaList(segments[0]);
+    return false;
 }
 
 template<typename T>
 static inline bool
 FinalizeTypedArenas(FreeOp *fop,
                     ArenaHeader **src,
-                    SortedArenaList &dest,
+                    ArenaList &dest,
                     AllocKind thingKind,
                     SliceBudget &budget)
 {
     /*
      * Finalize arenas from src list, releasing empty arenas and inserting the
-     * others into the appropriate destination size bins.
+     * others into dest in an appropriate position.
      */
 
     /*
      * During parallel sections, we sometimes finalize the parallel arenas,
      * but in that case, we want to hold on to the memory in our arena
      * lists, not offer it up for reuse.
      */
     bool releaseArenas = !InParallelSection();
 
     size_t thingSize = Arena::thingSize(thingKind);
-    size_t thingsPerArena = Arena::thingsPerArena(thingSize);
 
     while (ArenaHeader *aheader = *src) {
         *src = aheader->next;
-        size_t nmarked = aheader->getArena()->finalize<T>(fop, thingKind, thingSize);
-        size_t nfree = thingsPerArena - nmarked;
-
-        if (nmarked)
-            dest.insertAt(aheader, nfree);
+        bool allClear = aheader->getArena()->finalize<T>(fop, thingKind, thingSize);
+        if (!allClear)
+            dest.insertAtCursor(aheader);
         else if (releaseArenas)
             aheader->chunk()->releaseArena(aheader);
         else
-            aheader->chunk()->recycleArena(aheader, dest, thingKind, thingsPerArena);
-
-        budget.step(thingsPerArena);
+            aheader->chunk()->recycleArena(aheader, dest, thingKind);
+
+        budget.step(Arena::thingsPerArena(thingSize));
         if (budget.isOverBudget())
             return false;
     }
+    dest.deepCheck();
 
     return true;
 }
 
 /*
  * Finalize the list. On return, |al|'s cursor points to the first non-empty
  * arena in the list (which may be null if all arenas are full).
  */
 static bool
 FinalizeArenas(FreeOp *fop,
                ArenaHeader **src,
-               SortedArenaList &dest,
+               ArenaList &dest,
                AllocKind thingKind,
                SliceBudget &budget)
 {
     switch (thingKind) {
       case FINALIZE_OBJECT0:
       case FINALIZE_OBJECT0_BACKGROUND:
       case FINALIZE_OBJECT2:
       case FINALIZE_OBJECT2_BACKGROUND:
@@ -991,21 +960,20 @@ Chunk::addArenaToFreeList(JSRuntime *rt,
     aheader->next = info.freeArenasHead;
     info.freeArenasHead = aheader;
     ++info.numArenasFreeCommitted;
     ++info.numArenasFree;
     rt->gc.updateOnArenaFree(info);
 }
 
 void
-Chunk::recycleArena(ArenaHeader *aheader, SortedArenaList &dest, AllocKind thingKind,
-                    size_t thingsPerArena)
+Chunk::recycleArena(ArenaHeader *aheader, ArenaList &dest, AllocKind thingKind)
 {
     aheader->getArena()->setAsFullyUnused(thingKind);
-    dest.insertAt(aheader, thingsPerArena);
+    dest.insertAtCursor(aheader);
 }
 
 void
 Chunk::releaseArena(ArenaHeader *aheader)
 {
     JS_ASSERT(aheader->allocated());
     JS_ASSERT(!aheader->hasDelayedMarking);
     Zone *zone = aheader->zone;
@@ -1920,25 +1888,29 @@ ArenaLists::allocateFromArenaInline(Zone
     Chunk *chunk = rt->gc.pickChunk(zone, maybeStartBackgroundAllocation);
     if (!chunk)
         return nullptr;
 
     /*
      * While we still hold the GC lock get an arena from some chunk, mark it
      * as full as its single free span is moved to the free lists, and insert
      * it to the list as a fully allocated arena.
+     *
+     * We add the arena before the the head, so that after the GC the most
+     * recently added arena will be used first for allocations. This improves
+     * cache locality.
      */
     JS_ASSERT(al->isCursorAtEnd());
     aheader = chunk->allocateArena(zone, thingKind);
     if (!aheader)
         return nullptr;
 
     if (MOZ_UNLIKELY(zone->wasGCStarted()))
         rt->gc.arenaAllocatedDuringGC(zone, aheader);
-    al->insertAtCursor(aheader);
+    al->insertAtStart(aheader);
 
     /*
      * Allocate from a newly allocated arena. The arena will have been set up
      * as fully used during the initialization so we have to re-mark it as
      * empty before allocating.
      */
     JS_ASSERT(!aheader->hasFreeThings());
     Arena *arena = aheader->getArena();
@@ -2001,24 +1973,19 @@ ArenaLists::finalizeNow(FreeOp *fop, All
 void
 ArenaLists::forceFinalizeNow(FreeOp *fop, AllocKind thingKind)
 {
     JS_ASSERT(backgroundFinalizeState[thingKind] == BFS_DONE);
 
     ArenaHeader *arenas = arenaLists[thingKind].head();
     arenaLists[thingKind].clear();
 
-    size_t thingsPerArena = Arena::thingsPerArena(Arena::thingSize(thingKind));
-    SortedArenaList finalizedSorted(thingsPerArena);
-
     SliceBudget budget;
-    FinalizeArenas(fop, &arenas, finalizedSorted, thingKind, budget);
+    FinalizeArenas(fop, &arenas, arenaLists[thingKind], thingKind, budget);
     JS_ASSERT(!arenas);
-
-    arenaLists[thingKind] = finalizedSorted.toArenaList();
 }
 
 void
 ArenaLists::queueForForegroundSweep(FreeOp *fop, AllocKind thingKind)
 {
     JS_ASSERT(!IsBackgroundFinalized(thingKind));
     JS_ASSERT(backgroundFinalizeState[thingKind] == BFS_DONE);
     JS_ASSERT(!arenaListsToSweep[thingKind]);
@@ -2056,52 +2023,44 @@ ArenaLists::queueForBackgroundSweep(Free
 
 /*static*/ void
 ArenaLists::backgroundFinalize(FreeOp *fop, ArenaHeader *listHead, bool onBackgroundThread)
 {
     JS_ASSERT(listHead);
     AllocKind thingKind = listHead->getAllocKind();
     Zone *zone = listHead->zone;
 
-    size_t thingsPerArena = Arena::thingsPerArena(Arena::thingSize(thingKind));
-    SortedArenaList finalizedSorted(thingsPerArena);
-
+    ArenaList finalized;
     SliceBudget budget;
-    FinalizeArenas(fop, &listHead, finalizedSorted, thingKind, budget);
+    FinalizeArenas(fop, &listHead, finalized, thingKind, budget);
     JS_ASSERT(!listHead);
 
-    // When arenas are queued for background finalization, all arenas are moved
-    // to arenaListsToSweep[], leaving the arenaLists[] empty. However, new
-    // arenas may be allocated before background finalization finishes; now that
-    // finalization is complete, we want to merge these lists back together.
+    // When arenas are queued for background finalization, all
+    // arenas are moved to arenaListsToSweep[], leaving the arenaLists[] empty.
+    // Then, if new arenas are allocated before background finalization
+    // finishes they are always added to the front of the list. Therefore,
+    // at this point, |al|'s cursor will always be at the end of its list.
     ArenaLists *lists = &zone->allocator.arenas;
     ArenaList *al = &lists->arenaLists[thingKind];
 
-    // Flatten |finalizedSorted| into a regular ArenaList.
-    ArenaList finalized = finalizedSorted.toArenaList();
-
-    // Store this for later, since merging may change the state of |finalized|.
-    bool allClear = finalized.isEmpty();
-
     AutoLockGC lock(fop->runtime());
     JS_ASSERT(lists->backgroundFinalizeState[thingKind] == BFS_RUN);
 
-    // Join |al| and |finalized| into a single list.
-    *al = finalized.insertListWithCursorAtEnd(*al);
+    al->appendToListWithCursorAtEnd(finalized);
 
     /*
      * We must set the state to BFS_JUST_FINISHED if we are running on the
      * background thread and we have touched arenaList list, even if we add to
      * the list only fully allocated arenas without any free things. It ensures
      * that the allocation thread takes the GC lock and all writes to the free
      * list elements are propagated. As we always take the GC lock when
      * allocating new arenas from the chunks we can set the state to BFS_DONE if
      * we have released all finalized arenas back to their chunks.
      */
-    if (onBackgroundThread && !allClear)
+    if (onBackgroundThread && !finalized.isEmpty())
         lists->backgroundFinalizeState[thingKind] = BFS_JUST_FINISHED;
     else
         lists->backgroundFinalizeState[thingKind] = BFS_DONE;
 
     lists->arenaListsToSweep[thingKind] = nullptr;
 }
 
 void
@@ -4350,27 +4309,23 @@ GCRuntime::beginSweepPhase(bool lastGC)
 
     DropStringWrappers(rt);
     findZoneGroups();
     endMarkingZoneGroup();
     beginSweepingZoneGroup();
 }
 
 bool
-ArenaLists::foregroundFinalize(FreeOp *fop, AllocKind thingKind, SliceBudget &sliceBudget,
-                               SortedArenaList &sweepList)
-{
-    if (!FinalizeArenas(fop, &arenaListsToSweep[thingKind], sweepList, thingKind, sliceBudget))
-        return false;
-
-    // Join |arenaLists[thingKind]| and |sweepList| into a single list.
-    ArenaList finalized = sweepList.toArenaList();
-    arenaLists[thingKind] = finalized.insertListWithCursorAtEnd(arenaLists[thingKind]);
-
-    return true;
+ArenaLists::foregroundFinalize(FreeOp *fop, AllocKind thingKind, SliceBudget &sliceBudget)
+{
+    if (!arenaListsToSweep[thingKind])
+        return true;
+
+    ArenaList &dest = arenaLists[thingKind];
+    return FinalizeArenas(fop, &arenaListsToSweep[thingKind], dest, thingKind, sliceBudget);
 }
 
 bool
 GCRuntime::drainMarkStack(SliceBudget &sliceBudget, gcstats::Phase phase)
 {
     /* Run a marking slice and return whether the stack is now empty. */
     gcstats::AutoPhase ap(stats, phase);
     return marker.drainMarkStack(sliceBudget);
@@ -4392,27 +4347,19 @@ GCRuntime::sweepPhase(SliceBudget &slice
             gcstats::AutoPhase ap(stats, FinalizePhaseStatsPhase[finalizePhase]);
 
             for (; sweepZone; sweepZone = sweepZone->nextNodeInGroup()) {
                 Zone *zone = sweepZone;
 
                 while (sweepKindIndex < FinalizePhaseLength[finalizePhase]) {
                     AllocKind kind = FinalizePhases[finalizePhase][sweepKindIndex];
 
-                    /* Set the number of things per arena for this AllocKind. */
-                    size_t thingsPerArena = Arena::thingsPerArena(Arena::thingSize(kind));
-                    incrementalSweepList.setThingsPerArena(thingsPerArena);
-
-                    if (!zone->allocator.arenas.foregroundFinalize(&fop, kind, sliceBudget,
-                                                                   incrementalSweepList))
+                    if (!zone->allocator.arenas.foregroundFinalize(&fop, kind, sliceBudget))
                         return false;  /* Yield to the mutator. */
 
-                    /* Reset the slots of the sweep list that we used. */
-                    incrementalSweepList.reset(thingsPerArena);
-
                     ++sweepKindIndex;
                 }
                 sweepKindIndex = 0;
             }
             sweepZone = currentZoneGroup;
         }
 
         /* Remove dead shapes from the shape tree, but don't finalize them yet. */
@@ -5775,34 +5722,34 @@ ArenaLists::adoptArenas(JSRuntime *rt, A
         // When we enter a parallel section, we join the background
         // thread, and we do not run GC while in the parallel section,
         // so no finalizer should be active!
         normalizeBackgroundFinalizeState(AllocKind(thingKind));
         fromArenaLists->normalizeBackgroundFinalizeState(AllocKind(thingKind));
 #endif
         ArenaList *fromList = &fromArenaLists->arenaLists[thingKind];
         ArenaList *toList = &arenaLists[thingKind];
-        fromList->check();
-        toList->check();
+        fromList->deepCheck();
+        toList->deepCheck();
         ArenaHeader *next;
         for (ArenaHeader *fromHeader = fromList->head(); fromHeader; fromHeader = next) {
             // Copy fromHeader->next before releasing/reinserting.
             next = fromHeader->next;
 
             // During parallel execution, we sometimes keep empty arenas
             // on the lists rather than sending them back to the chunk.
             // Therefore, if fromHeader is empty, send it back to the
             // chunk now. Otherwise, attach to |toList|.
             if (fromHeader->isEmpty())
                 fromHeader->chunk()->releaseArena(fromHeader);
             else
                 toList->insertAtCursor(fromHeader);
         }
         fromList->clear();
-        toList->check();
+        toList->deepCheck();
     }
 }
 
 bool
 ArenaLists::containsArena(JSRuntime *rt, ArenaHeader *needle)
 {
     AutoLockGC lock(rt);
     size_t allocKind = needle->getAllocKind();
--- a/js/src/jsgc.h
+++ b/js/src/jsgc.h
@@ -378,100 +378,16 @@ GetGCKindSlots(AllocKind thingKind, cons
 }
 
 // Class to assist in triggering background chunk allocation. This cannot be done
 // while holding the GC or worker thread state lock due to lock ordering issues.
 // As a result, the triggering is delayed using this class until neither of the
 // above locks is held.
 class AutoMaybeStartBackgroundAllocation;
 
-// A single segment of a SortedArenaList. Each segment has a head and a tail,
-// which track the start and end of a segment for O(1) append and concatenation.
-struct SortedArenaListSegment
-{
-    ArenaHeader *head;
-    ArenaHeader **tailp;
-
-    void clear() {
-        head = nullptr;
-        tailp = &head;
-    }
-
-    bool isEmpty() const {
-        return tailp == &head;
-    }
-
-    // Appends |aheader| to this segment.
-    void append(ArenaHeader *aheader) {
-        JS_ASSERT(aheader);
-        JS_ASSERT_IF(head, head->getAllocKind() == aheader->getAllocKind());
-        *tailp = aheader;
-        tailp = &aheader->next;
-    }
-
-    // Points the tail of this segment at |aheader|, which may be null.
-    void linkTo(ArenaHeader *aheader) {
-        *tailp = aheader;
-    }
-};
-
-// A class that holds arenas in sorted order by appending arenas to specific
-// segments. SortedArenaLists can be flattened to a regular ArenaList.
-class SortedArenaList
-{
-  public:
-    // The minimum size, in bytes, of a GC thing.
-    static const size_t MinThingSize = 16;
-
-    static_assert(ArenaSize <= 4096, "When increasing the Arena size, please consider how"\
-                                     " this will affect the size of a SortedArenaList.");
-
-    static_assert(MinThingSize >= 16, "When decreasing the minimum thing size, please consider"\
-                                      " how this will affect the size of a SortedArenaList.");
-
-  private:
-    // The maximum number of GC things that an arena can hold.
-    static const size_t MaxThingsPerArena = (ArenaSize - sizeof(ArenaHeader)) / MinThingSize;
-
-    size_t thingsPerArena_;
-    SortedArenaListSegment segments[MaxThingsPerArena + 1];
-
-    // Convenience functions to get the nth head and tail.
-    ArenaHeader *headAt(size_t n) { return segments[n].head; }
-    ArenaHeader **tailAt(size_t n) { return segments[n].tailp; }
-
-  public:
-    explicit SortedArenaList(size_t thingsPerArena = MaxThingsPerArena) {
-        reset(thingsPerArena);
-    }
-
-    void setThingsPerArena(size_t thingsPerArena) {
-        JS_ASSERT(thingsPerArena && thingsPerArena <= MaxThingsPerArena);
-        thingsPerArena_ = thingsPerArena;
-    }
-
-    // Resets the first |thingsPerArena| segments of this list for further use.
-    void reset(size_t thingsPerArena = MaxThingsPerArena) {
-        setThingsPerArena(thingsPerArena);
-        // Initialize the segments.
-        for (size_t i = 0; i <= thingsPerArena; ++i)
-            segments[i].clear();
-    }
-
-    // Inserts a header, which has room for |nfree| more things, in its segment.
-    void insertAt(ArenaHeader *aheader, size_t nfree) {
-        JS_ASSERT(nfree <= thingsPerArena_);
-        segments[nfree].append(aheader);
-    }
-
-    // Flattens the SortedArenaList into a regular ArenaList. Although we don't
-    // expect to do this more than once, note this operation is not destructive.
-    ArenaList toArenaList();
-};
-
 /*
  * Arena lists have a head and a cursor. The cursor conceptually lies on arena
  * boundaries, i.e. before the first arena, between two arenas, or after the
  * last arena.
  *
  * Normally the arena following the cursor is the first arena in the list with
  * some free things and all arenas before the cursor are fully allocated. (And
  * if the cursor is at the end of the list, then all the arenas are full.)
@@ -504,55 +420,55 @@ class ArenaList {
     //     cursor, and therefore |*cursorp_| points to the arena following the
     //     cursor.
     //
     // |cursorp_| is never null.
     //
     ArenaHeader     *head_;
     ArenaHeader     **cursorp_;
 
-    void copy(const ArenaList &other) {
-        other.check();
-        head_ = other.head_;
-        cursorp_ = other.isCursorAtHead() ? &head_ : other.cursorp_;
-        check();
-    }
-
   public:
     ArenaList() {
         clear();
     }
 
-    ArenaList(const ArenaList &other) {
-        copy(other);
-    }
-
-    ArenaList &operator=(const ArenaList &other) {
-        copy(other);
-        return *this;
-    }
-    
-    ArenaList(const SortedArenaListSegment &segment) {
-        head_ = segment.head;
-        cursorp_ = segment.isEmpty() ? &head_ : segment.tailp;
-        check();
-    }
-    
     // This does checking just of |head_| and |cursorp_|.
     void check() const {
 #ifdef DEBUG
         // If the list is empty, it must have this form.
         JS_ASSERT_IF(!head_, cursorp_ == &head_);
 
         // If there's an arena following the cursor, it must not be full.
         ArenaHeader *cursor = *cursorp_;
         JS_ASSERT_IF(cursor, cursor->hasFreeThings());
 #endif
     }
 
+    // This does checking involving all the arenas in the list.
+    void deepCheck() const {
+#ifdef DEBUG
+        check();
+        // All full arenas must precede all non-full arenas.
+        //
+        // XXX: this is currently commented out because it fails moderately
+        // often. I'm not sure if this is because (a) it's not true that all
+        // full arenas must precede all non-full arenas, or (b) we have some
+        // defective list-handling code.
+        //
+//      bool havePassedFullArenas = false;
+//      for (ArenaHeader *aheader = head_; aheader; aheader = aheader->next) {
+//          if (havePassedFullArenas) {
+//              JS_ASSERT(aheader->hasFreeThings());
+//          } else if (aheader->hasFreeThings()) {
+//              havePassedFullArenas = true;
+//          }
+//      }
+#endif
+    }
+
     void clear() {
         head_ = nullptr;
         cursorp_ = &head_;
         check();
     }
 
     bool isEmpty() const {
         check();
@@ -560,21 +476,16 @@ class ArenaList {
     }
 
     // This returns nullptr if the list is empty.
     ArenaHeader *head() const {
         check();
         return head_;
     }
 
-    bool isCursorAtHead() const {
-        check();
-        return cursorp_ == &head_;
-    }
-
     bool isCursorAtEnd() const {
         check();
         return !*cursorp_;
     }
 
     // This can return nullptr.
     ArenaHeader *arenaAfterCursor() const {
         check();
@@ -599,29 +510,43 @@ class ArenaList {
         *cursorp_ = a;
         // At this point, the cursor is sitting before |a|. Move it after |a|
         // if necessary.
         if (!a->hasFreeThings())
             cursorp_ = &a->next;
         check();
     }
 
-    // This inserts |other|, which must be full, at the cursor of |this|.
-    ArenaList &insertListWithCursorAtEnd(const ArenaList &other) {
+    // This inserts |a| at the start of the list, and doesn't change the
+    // cursor.
+    void insertAtStart(ArenaHeader *a) {
+        check();
+        a->next = head_;
+        if (isEmpty())
+            cursorp_ = &a->next;        // The cursor remains null.
+        head_ = a;
         check();
-        other.check();
-        JS_ASSERT(other.isCursorAtEnd());
-        if (other.isCursorAtHead())
-            return *this;
-        // Insert the full arenas of |other| after those of |this|.
-        *other.cursorp_ = *cursorp_;
-        *cursorp_ = other.head_;
-        cursorp_ = other.cursorp_;
-        check();
-        return *this;
+    }
+
+    // Appends |list|. |this|'s cursor must be at the end.
+    void appendToListWithCursorAtEnd(ArenaList &other) {
+        JS_ASSERT(isCursorAtEnd());
+        deepCheck();
+        other.deepCheck();
+        if (!other.isEmpty()) {
+            // Because |this|'s cursor is at the end, |cursorp_| points to the
+            // list-ending null. So this assignment appends |other| to |this|.
+            *cursorp_ = other.head_;
+
+            // If |other|'s cursor isn't at the start of the list, then update
+            // |this|'s cursor accordingly.
+            if (other.cursorp_ != &other.head_)
+                cursorp_ = other.cursorp_;
+        }
+        deepCheck();
     }
 };
 
 class ArenaLists
 {
     /*
      * For each arena kind its free list is represented as the first span with
      * free things. Initially all the spans are initialized as empty. After we
@@ -870,18 +795,17 @@ class ArenaLists
     }
 
     void queueObjectsForSweep(FreeOp *fop);
     void queueStringsAndSymbolsForSweep(FreeOp *fop);
     void queueShapesForSweep(FreeOp *fop);
     void queueScriptsForSweep(FreeOp *fop);
     void queueJitCodeForSweep(FreeOp *fop);
 
-    bool foregroundFinalize(FreeOp *fop, AllocKind thingKind, SliceBudget &sliceBudget,
-                            SortedArenaList &sweepList);
+    bool foregroundFinalize(FreeOp *fop, AllocKind thingKind, SliceBudget &sliceBudget);
     static void backgroundFinalize(FreeOp *fop, ArenaHeader *listHead, bool onBackgroundThread);
 
     void wipeDuringParallelExecution(JSRuntime *rt);
 
   private:
     inline void finalizeNow(FreeOp *fop, AllocKind thingKind);
     inline void forceFinalizeNow(FreeOp *fop, AllocKind thingKind);
     inline void queueForForegroundSweep(FreeOp *fop, AllocKind thingKind);