Changeset 26618 in webkit for trunk/JavaScriptCore


Ignore:
Timestamp:
Oct 15, 2007, 1:39:10 PM (18 years ago)
Author:
ggaren
Message:

Reviewed by Maciej Stachowiak.


Some Vector optimizations. These are especially important when using
Vector as a stack for implementing recursive algorithms iteratively.


[ Broken off from ​http://bugs.webkit.org/show_bug.cgi?id=14868 ]

  1. Added shrink(), which is a version of resize() that you can call to save a branch / improve code generation and inlining when you know that the vector is not getting bigger.


  1. Changed subclassing relationship in VectorBuffer to remove a call to fastFree() in the destructor for the inlineCapacity != 0 template specialization. This brings inline Vectors one step closer to true stack-allocated arrays.


Also changed abort() to CRASH(), since the latter works better.

  • wtf/Vector.h: (WTF::VectorBufferBase::allocateBuffer): (WTF::VectorBufferBase::deallocateBuffer): (WTF::VectorBufferBase::VectorBufferBase): (WTF::VectorBufferBase::~VectorBufferBase): (WTF::): (WTF::VectorBuffer::VectorBuffer): (WTF::VectorBuffer::~VectorBuffer): (WTF::VectorBuffer::deallocateBuffer): (WTF::VectorBuffer::releaseBuffer): (WTF::Vector::clear): (WTF::Vector::removeLast): (WTF::::operator): (WTF::::fill): (WTF::::shrink):
Location:
trunk/JavaScriptCore
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/ChangeLog

    r26617 r26618  
     12007-10-15  Geoffrey Garen  <[email protected]>
     2
     3        Reviewed by Maciej Stachowiak.
     4       
     5        Some Vector optimizations. These are especially important when using
     6        Vector as a stack for implementing recursive algorithms iteratively.
     7       
     8        [ Broken off from http://bugs.webkit.org/show_bug.cgi?id=14868 ]
     9
     10        1. Added shrink(), which is a version of resize() that you can call
     11        to save a branch / improve code generation and inlining when you know
     12        that the vector is not getting bigger.
     13       
     14        2. Changed subclassing relationship in VectorBuffer to remove a call to
     15        fastFree() in the destructor for the inlineCapacity != 0 template
     16        specialization. This brings inline Vectors one step closer to true
     17        stack-allocated arrays.
     18       
     19        Also changed abort() to CRASH(), since the latter works better.
     20
     21        * wtf/Vector.h:
     22        (WTF::VectorBufferBase::allocateBuffer):
     23        (WTF::VectorBufferBase::deallocateBuffer):
     24        (WTF::VectorBufferBase::VectorBufferBase):
     25        (WTF::VectorBufferBase::~VectorBufferBase):
     26        (WTF::):
     27        (WTF::VectorBuffer::VectorBuffer):
     28        (WTF::VectorBuffer::~VectorBuffer):
     29        (WTF::VectorBuffer::deallocateBuffer):
     30        (WTF::VectorBuffer::releaseBuffer):
     31        (WTF::Vector::clear):
     32        (WTF::Vector::removeLast):
     33        (WTF::::operator):
     34        (WTF::::fill):
     35        (WTF::::shrink):
     36
    1372007-10-12  Geoffrey Garen  <[email protected]>
    238

  • trunk/JavaScriptCore/wtf/Vector.h

    r26182 r26618  
    241241    };
    242242
    243     template<typename T, size_t inlineCapacity>
    244     class VectorBuffer;
    245 
    246     template<typename T>
    247     class VectorBuffer<T, 0> {
     243    template<typename T>
     244    class VectorBufferBase {
    248245    public:
    249         VectorBuffer()
    250             : m_buffer(0), m_capacity(0)
    251         {
    252         }
    253        
    254         VectorBuffer(size_t capacity)
    255 #if !ASSERT_DISABLED
    256             : m_capacity(0)
    257 #endif
    258         {
    259             allocateBuffer(capacity);
    260         }
    261 
    262         ~VectorBuffer()
    263         {
    264             deallocateBuffer(m_buffer);
    265         }
    266        
    267         static void deallocateBuffer(T* buffer)
    268         {
    269             fastFree(buffer);
    270         }
    271        
    272246        void allocateBuffer(size_t newCapacity)
    273247        {
    … …  
    275249            m_capacity = newCapacity;
    276250            if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
    277                 abort();
     251                CRASH();
    278252            m_buffer = static_cast<T*>(fastMalloc(newCapacity * sizeof(T)));
     253        }
     254
     255        void deallocateBuffer(T* bufferToDeallocate)
     256        {
     257            fastFree(bufferToDeallocate);
    279258        }
    280259
    … …  
    282261        const T* buffer() const { return m_buffer; }
    283262        size_t capacity() const { return m_capacity; }
    284 
    285         void swap(VectorBuffer<T, 0>& other)
    286         {
    287             std::swap(m_capacity, other.m_capacity);
    288             std::swap(m_buffer, other.m_buffer);
    289         }
    290263
    291264        T* releaseBuffer()
    … …  
    298271
    299272    protected:
    300         VectorBuffer(T* buffer, size_t capacity)
    301             : m_buffer(buffer), m_capacity(capacity)
    302         {
     273        VectorBufferBase()
     274            : m_buffer(0)
     275            , m_capacity(0)
     276        {
     277        }
     278
     279        VectorBufferBase(T* buffer, size_t capacity)
     280            : m_buffer(buffer)
     281            , m_capacity(capacity)
     282        {
     283        }
     284
     285        ~VectorBufferBase()
     286        {
     287            // FIXME: It would be nice to find a way to ASSERT that m_buffer hasn't leaked here.
    303288        }
    304289
    305290        T* m_buffer;
    306 
     291        size_t m_capacity;
     292    };
     293
     294    template<typename T, size_t inlineCapacity>
     295    class VectorBuffer;
     296
     297    template<typename T>
     298    class VectorBuffer<T, 0> : private VectorBufferBase<T> {
    307299    private:
    308         size_t m_capacity;
    309     };
    310 
    311     template<typename T, size_t inlineCapacity>
    312     class VectorBuffer : private VectorBuffer<T, 0> {
    313     private:
    314         typedef VectorBuffer<T, 0> BaseBuffer;
     300        typedef VectorBufferBase<T> Base;
    315301    public:
    316302        VectorBuffer()
    317             : BaseBuffer(inlineBuffer(), inlineCapacity)
    318303        {
    319304        }
    320305
    321306        VectorBuffer(size_t capacity)
    322             : BaseBuffer(inlineBuffer(), inlineCapacity)
     307        {
     308            allocateBuffer(capacity);
     309        }
     310
     311        ~VectorBuffer()
     312        {
     313            deallocateBuffer(buffer());
     314        }
     315       
     316        void swap(VectorBuffer<T, 0>& other)
     317        {
     318            std::swap(m_buffer, other.m_buffer);
     319            std::swap(m_capacity, other.m_capacity);
     320        }
     321
     322        using Base::allocateBuffer;
     323        using Base::deallocateBuffer;
     324
     325        using Base::buffer;
     326        using Base::capacity;
     327
     328        using Base::releaseBuffer;
     329    private:
     330        using Base::m_buffer;
     331        using Base::m_capacity;
     332    };
     333
     334    template<typename T, size_t inlineCapacity>
     335    class VectorBuffer : private VectorBufferBase<T> {
     336    private:
     337        typedef VectorBufferBase<T> Base;
     338    public:
     339        VectorBuffer()
     340            : Base(inlineBuffer(), inlineCapacity)
     341        {
     342        }
     343
     344        VectorBuffer(size_t capacity)
     345            : Base(inlineBuffer(), inlineCapacity)
    323346        {
    324347            if (capacity > inlineCapacity)
    … …  
    328351        ~VectorBuffer()
    329352        {
    330             if (buffer() == inlineBuffer())
    331                 BaseBuffer::m_buffer = 0;
    332         }
    333 
    334         void deallocateBuffer(T* buffer)
    335         {
    336             if (buffer != inlineBuffer())
    337                 BaseBuffer::deallocateBuffer(buffer);
    338         }
    339 
    340         using BaseBuffer::allocateBuffer;
    341 
    342         using BaseBuffer::buffer;
    343         using BaseBuffer::capacity;
     353            deallocateBuffer(buffer());
     354        }
     355
     356        using Base::allocateBuffer;
     357
     358        void deallocateBuffer(T* bufferToDeallocate)
     359        {
     360            if (bufferToDeallocate == inlineBuffer())
     361                return;
     362            Base::deallocateBuffer(bufferToDeallocate);
     363        }
     364
     365        using Base::buffer;
     366        using Base::capacity;
    344367
    345368        T* releaseBuffer()
    … …  
    347370            if (buffer() == inlineBuffer())
    348371                return 0;
    349             return BaseBuffer::releaseBuffer();
    350         }
    351 
    352         void swap(VectorBuffer<T, inlineCapacity>&);
     372            return Base::releaseBuffer();
     373        }
    353374
    354375    private:
     376        using Base::m_buffer;
     377        using Base::m_capacity;
     378
    355379        static const size_t m_inlineBufferSize = inlineCapacity * sizeof(T);
    356380        T* inlineBuffer() { return reinterpret_cast<T*>(&m_inlineBuffer); }
    … …  
    425449        const T& last() const { return at(size() - 1); }
    426450
     451        void shrink(size_t size);
    427452        void resize(size_t size);
    428453        void reserveCapacity(size_t newCapacity);
    429454
    430         void clear() { resize(0); }
     455        void clear() { shrink(0); }
    431456
    432457        template<typename U> void append(const U*, size_t);
    … …  
    447472        {
    448473            ASSERT(!isEmpty());
    449             resize(size() - 1);
     474            shrink(size() - 1);
    450475        }
    451476
    … …  
    503528       
    504529        if (size() > other.size())
    505             resize(other.size());
     530            shrink(other.size());
    506531        else if (other.size() > capacity()) {
    507532            clear();
    … …  
    524549       
    525550        if (size() > other.size())
    526             resize(other.size());
     551            shrink(other.size());
    527552        else if (other.size() > capacity()) {
    528553            clear();
    … …  
    541566    {
    542567        if (size() > newSize)
    543             resize(newSize);
     568            shrink(newSize);
    544569        else if (newSize > capacity()) {
    545570            clear();
    … …  
    596621        }
    597622       
     623        m_size = size;
     624    }
     625
     626    template<typename T, size_t inlineCapacity>
     627    void Vector<T, inlineCapacity>::shrink(size_t size)
     628    {
     629        ASSERT(size <= m_size);
     630        TypeOperations::destruct(begin() + size, end());
    598631        m_size = size;
    599632    }
Note: See TracChangeset for help on using the changeset viewer.