Bug 18672 – SQUIRRELFISH: codegen fails with a large number of temporaries

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Cameron Zwarich (cpst)]

On a number of the JavaScriptCore tests, SquirrelFish fails with an assertion during codegen if there is a large number of temporaries. These failures do not get seem to get reported by run-javascriptcore-tests. An example is ecma/Array/15.4.5.2-2.js, which fails with the following assertion:

ASSERTION FAILED: m_temporaries.size() < m_temporaries.capacity()
(./VM/CodeGenerator.cpp:296 KJS::RegisterID* KJS::CodeGenerator::newTemporary())

Many of the array tests fail for the same reason.

[Maciej Stachowiak]

Geoff and I agree that a good way to do this would be to use a segmented array for the temporaries (so they don't move but we still have the ability to allocate more).

[Cameron Zwarich (cpst)]

(In reply to comment #1)
> Geoff and I agree that a good way to do this would be to use a segmented array
> for the temporaries (so they don't move but we still have the ability to
> allocate more).

I agree with this suggestion.

[Oliver Hunt]

Created attachment 20763 [details]
Patch-fu!

[Oliver Hunt]

Created attachment 20766 [details]
Second run

Second run, now actually returns memory, SunSpider reports a 0.4% progression but that seems unlikely to be "real"

[Geoffrey Garen]

Comment on attachment 20766 [details]
Second run

+		A7C31DA90DBEBA4300FDF8EB /* SegmentedVector.h in Headers */ = {isa = PBXBuildFile; fileRef = A7C31DA80DBEBA4300FDF8EB /* SegmentedVector.h */; };
+		A7C31DAA0DBEBA4300FDF8EB /* SegmentedVector.h in Headers */ = {isa = PBXBuildFile; fileRef = A7C31DA80DBEBA4300FDF8EB /* SegmentedVector.h */; };

SegmentedVector is really a component of the compiler, not the VM. I think it
belongs in the compiler folder.

+            if (!(m_size % SegmentSize) && m_size >= SegmentSize)

Would

if (!(m_size % SegmentSize) && m_size > 0)

do the same job? If so, I think it would be clearer.

+        void removeLast()
+        {
+            ASSERT(m_size);
+            m_size--;
+            m_buffers.last()->removeLast();
+            if (!(m_size % SegmentSize) && m_size >= SegmentSize) {
+                delete m_buffers.last();
+                m_buffers.removeLast();
+            }
+        }

Technically, if you kept adding and removing an item at the segement boundary,
this algorithm would give you really bad performance, because it would
repeatedly malloc/free a large block. You could fix the problem by keeping a
size and a capacity, just like Vector does. I don't think this is a blocker to
landing, though, since you'd have to get pretty unlucky to hit this case during
codegen.

+            if (index < SegmentSize)
+                return m_inlineBuffer[index];
+            return m_buffers[index / SegmentSize]->at(index % SegmentSize);

Why do we need to special-case the inline buffer here? Shouldn't the math "just
work"? I'd recommend removing the special case.

+        void shrink(size_t size)
+        {
...
+        }
+
+        void grow(size_t size)
+        {
...
+        }

These methods look a little long for inlining. I'd recommend moving them out of
the class declaration.

+        void grow(size_t size)
+        {
+            ASSERT(size > m_size);
+            if (size <= SegmentSize) {
+                m_inlineBuffer.resize(size);

You can call "grow" here instead of "resize". Same thing in a few other places
in this function.

+        Segment m_inlineBuffer;
+        Vector<Segment*, 32> m_buffers;

Quibble: is it a "segment" or a "buffer"? I would call these "m_inlineSegment"
and "m_segments".

Nice work.

r=me

[Oliver Hunt]

> SegmentedVector is really a component of the compiler, not the VM. I think it
> belongs in the compiler folder.
>
There is no Compiler directory -- I did put it in the Compiler group (in xcode), other things (like CodeGenerator.{h,cpp} are there as well.
 
> +            if (!(m_size % SegmentSize) && m_size >= SegmentSize)
> 
> Would
> 
> if (!(m_size % SegmentSize) && m_size > 0)

Fixed

> 
> do the same job? If so, I think it would be clearer.
> 
> +        void removeLast()
> +        {
> +            ASSERT(m_size);
> +            m_size--;
> +            m_buffers.last()->removeLast();
> +            if (!(m_size % SegmentSize) && m_size >= SegmentSize) {
> +                delete m_buffers.last();
> +                m_buffers.removeLast();
> +            }
> +        }
> 
> Technically, if you kept adding and removing an item at the segement boundary,
> this algorithm would give you really bad performance, because it would
> repeatedly malloc/free a large block. You could fix the problem by keeping a
> size and a capacity, just like Vector does. I don't think this is a blocker to
> landing, though, since you'd have to get pretty unlucky to hit this case during
> codegen.

Yeah, i know, however in the general case you do not have 512 temporaries so i thought this would be okay (at least for now)

> 
> +            if (index < SegmentSize)
> +                return m_inlineBuffer[index];
> +            return m_buffers[index / SegmentSize]->at(index % SegmentSize);
> 
> Why do we need to special-case the inline buffer here? Shouldn't the math "just
> work"? I'd recommend removing the special case.
Performance, no other reason

> 
> +        void shrink(size_t size)
> +        {
> ...
> +        }
> +
> +        void grow(size_t size)
> +        {
> ...
> +        }
> 
> These methods look a little long for inlining. I'd recommend moving them out of
> the class declaration.
> 
> +        void grow(size_t size)
> +        {
> +            ASSERT(size > m_size);
> +            if (size <= SegmentSize) {
> +                m_inlineBuffer.resize(size);
> 
> You can call "grow" here instead of "resize". Same thing in a few other places
> in this function.

That's a perf regression :-/

> 
> +        Segment m_inlineBuffer;
> +        Vector<Segment*, 32> m_buffers;
> 
> Quibble: is it a "segment" or a "buffer"? I would call these "m_inlineSegment"
> and "m_segments".

Agreed, and m_inlineSegment for good measure

> 
> Nice work.
> 
> r=me
> 

Committer r32444