Bug 24739 - Combine StringImpl struct and data allocations
Summary: Combine StringImpl struct and data allocations
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Platform (show other bugs)
Version: 528+ (Nightly build)
Hardware: Mac OS X 10.5
: P2 Normal
Assignee: Mike Belshe
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2009-03-21 03:29 PDT by Mike Belshe
Modified: 2009-03-23 13:28 PDT (History)
0 users

See Also:


Attachments
patch (5.66 KB, patch)
2009-03-21 03:35 PDT, Mike Belshe
darin: review-
Details | Formatted Diff | Diff
updated patch to address comments. (7.46 KB, patch)
2009-03-21 19:42 PDT, Mike Belshe
darin: review+
Details | Formatted Diff | Diff
patch with Darin's comments (7.48 KB, patch)
2009-03-23 12:38 PDT, Mike Belshe
fishd: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Mike Belshe 2009-03-21 03:29:56 PDT
Often when we create a StringImpl(), we know what data it is going to contain.  Currently, this results in two heap allocations - one for the StringImpl class, and a second for the data.  These can be combined into a single allocation.

I measured small performance increases, but it is hard to be certain that these are not in the noise.  Nonetheless, it is more efficient.
Comment 1 Mike Belshe 2009-03-21 03:35:02 PDT
Created attachment 28821 [details]
patch
Comment 2 Mike Belshe 2009-03-21 03:45:34 PDT
Requesting review from Maciej - I suspect he will know if there is some reason this doesn't work well. 

Tests I ran:  passes all layout tests, sunspider benchmark, independent tests.

This does add a flag into the StringImpl, but doesn't increase the size of the StringImpl because of padding.
Comment 3 Darin Adler 2009-03-21 07:40:13 PDT
Comment on attachment 28821 [details]
patch

> +        Rework StringImpl::create methods to try to allocate
> +        a single buffer rahter than allocating both the StringImpl class
> +        and a separate data buffer.

I like this idea! Seems like a good approach that will save us quite a bit of memory.

> +    // Allocate a single buffer large enough to contain the StringImpl
> +    // struct as well as the data which it contains.  This removes one 
> +    // heap allocation from this call.
> +    int size = sizeof(StringImpl) + (length * sizeof(UChar));
> +    char* buffer = static_cast<char*>(fastMalloc(size));
> +    UChar* data = reinterpret_cast<UChar*>(buffer + sizeof(StringImpl));
> +    memcpy(data, characters, length * sizeof(UChar));
> +    StringImpl* rv = new (buffer) StringImpl(data, length, AdoptBuffer());
> +    rv->m_internalBuffer = true;
> +    return adoptRef(rv);

If we’ve created a StringImpl this way, then we can’t just delete it with a “delete” call. Instead we need to separately call the destructor and then call fastFree. As you can see in https://bugs.webkit.org/show_bug.cgi?id=22834 and http://trac.webkit.org/changeset/41877 if we mismatch fastMalloc and delete we will end up causing trouble for valgrind.

But it’s relatively easy to fix. We can always use fastMalloc and placement new to allocate StringImpl, even when the buffer is not internal, and then we can implement our own deletion that uses fastFree instead of delete. The way to implement our own deletion is to inherit from RefCountedBase instead of from RefCounted<StringImpl> and then write our own deref function:

    void deref() {
        if (derefBase()) {
            this->~StringImpl();
            fastFree(this);
        }
    }

Also, WebKit code would normally use a name like "string" rather than "rv" for the newly created StringImpl.

> +    // In some cases, we allocate the StringImpl struct and its data
> +    // within a single heap buffer.  In this case, the m_data pointer
> +    // is an "internal buffer", and does not need to be deallocated.
> +    bool m_internalBuffer;

m_internalBuffer is a good name for a buffer, but not a good name for a boolean telling you the type of buffer. m_bufferIsInternal or m_isInternalBuffer would be a better name for a boolean. But I don't think we need the boolean. You can write it like this:

    if (m_data != reinterpret_cast<UChar*>(this + 1))
        deleteUCharVector(m_data);

I think it’s better for the future to not have a boolean for this, even though at the moment we can afford it. Not having to set that boolean will streamline the creation code a bit too.

I’m going to say review- because of the easily-fixable fastMalloc/delete mismatch.
Comment 4 Mike Belshe 2009-03-21 11:01:27 PDT
Thanks for the comments Darin - those all sound fine.  I'll get those things cleaned up and push up a new patch after testing.
Comment 5 Mike Belshe 2009-03-21 11:17:43 PDT
I think we should still use the flag.  Although it is highly unlikely (and perhaps impossible in most cases), there is no guarantee that just because the data points to the space immediately following the StringImpl that the buffer is part of a single buffer.

e.g.
   StringImpl = new....   could return 0x00001000
   char* data = new...    could return 0x00001010

The flag is the only way to know that we need two deletes for this case.
Comment 6 Mike Belshe 2009-03-21 19:42:14 PDT
Created attachment 28828 [details]
updated patch to address comments.

Addressed the naming issues.
Did not remove the boolean because of previous comment; the fact that the address of the buffer starts immediately after the StringImpl is not a guarantee that it was allocated in one chunk.
Took a different approach to solving the valgrind mis-matched free problem.  Since we really want this class to control how the StringImpl is allocated, overriding new & delete works well.
Comment 7 Darin Adler 2009-03-23 08:53:42 PDT
Comment on attachment 28828 [details]
updated patch to address comments.

> +// Some of the factory methods create buffers using fastMalloc.
> +// We must ensure that all allocations of StringImpl are allocated using
> +// fastMalloc so that we don't have mis-matched frees.   We accomplish 
> +// this by overriding the new and delete operators.

We use one space after a period, not three.

> +void *StringImpl::operator new(size_t bytes, void *mem)

We use void*, not void *.

The name "bytes" seems wrong for the argument, since the argument is a number of bytes, not actual "bytes". Perhaps the name "size" or "sizeInBytes".

I'm not sure why you chose to abbreviate "memory" to "mem", but please don't.

> +void *StringImpl::operator new(size_t bytes)

Again, void*.

> +    // Allocate a single buffer large enough to contain the StringImpl
> +    // struct as well as the data which it contains.  This removes one 
> +    // heap allocation from this call.

One space, not two, after a period.

> +    int size = sizeof(StringImpl) + (length * sizeof(UChar));

size_t, not int. Also, I don't think the parentheses make things clearer and I would omit them.

> +    // Allocate a single buffer large enough to contain the StringImpl
> +    // struct as well as the data which it contains.  This removes one 
> +    // heap allocation from this call.

One space, not two.

> +    int size = sizeof(StringImpl) + (length * sizeof(UChar));

size_t, not int. Also, I don't think the parentheses make things clearer and I would omit them.

> +    void *operator new(size_t bytes);

void*, not void *. Same comment as above about the argument name "bytes".

> +    // Allocation from a custom buffer is only allowed internally to avoid
> +    // mismatched allocators.
> +    void *operator new(size_t bytes, void *mem);

This comment seems a little strange. All allocation is only allowed internally. Can't you make all the operator new declarations private?

void*, not void *. Same comment as above about the argument name "bytes".

> +    // In some cases, we allocate the StringImpl struct and its data
> +    // within a single heap buffer.  In this case, the m_data pointer
> +    // is an "internal buffer", and does not need to be deallocated.

One space, not two, after a period.

r=me as is -- the comments above are all minor nitpicks
Comment 8 Mike Belshe 2009-03-23 12:38:49 PDT
Created attachment 28862 [details]
patch with Darin's comments

Thanks for the comments; sorry about the stupid nits.

I moved both operator new() calls to be private; I hadn't done this before to be conservative.  But after re-testing, all callers are using the create() methods (which is good!), so I was able to make this private.
Comment 9 Darin Fisher (:fishd, Google) 2009-03-23 12:44:22 PDT
Comment on attachment 28862 [details]
patch with Darin's comments

carrying forward Darin Adler's r+.
Comment 10 Darin Adler 2009-03-23 12:51:31 PDT
Comment on attachment 28862 [details]
patch with Darin's comments

Still great.

> +        Rework StringImpl::create methods to try to allocate
> +        a single buffer rahter than allocating both the StringImpl class
> +        and a separate data buffer.

Typo here: "rahter".

> +    // Allocation from a custom buffer is only allowed internally to avoid
> +    // mismatched allocators.  Callers should use create().

Still two spaces after the period here.

> +    void* operator new(size_t size);
> +    void* operator new(size_t size, void* mem);

Still "mem" here, instead of a word. Same in one other place.
Comment 11 Darin Fisher (:fishd, Google) 2009-03-23 13:28:11 PDT
Landed as:  http://trac.webkit.org/changeset/41917

mem -> address