Implement external strings.

runtime/include/dart_api.h

Index: runtime/include/dart_api.h
diff --git a/runtime/include/dart_api.h b/runtime/include/dart_api.h
index c8faf4fbde751742299289e6213915e9d902c68a..59d410c89da0d6578dc77f59c1fbbb3bc513f8a7 100755
--- a/runtime/include/dart_api.h
+++ b/runtime/include/dart_api.h
@@ -98,6 +98,10 @@ typedef Dart_Result (*Dart_LibraryTagHandler)(Dart_LibraryTag tag,
                                               Dart_Handle library,
                                               Dart_Handle url);
 
+typedef void (*Dart_ExternalString8Finalizer)(uint8_t* codepoints);
+typedef void (*Dart_ExternalString16Finalizer)(uint16_t* codepoints);
+typedef void (*Dart_ExternalString32Finalizer)(uint32_t* codepoints);
+
 // TODO(iposva): This is a placeholder for the eventual external Dart API.
 
 // Return value handling after a Dart API call.
@@ -293,6 +297,20 @@ DART_EXPORT Dart_Handle Dart_NewString16(const uint16_t* codepoints,
 DART_EXPORT Dart_Handle Dart_NewString32(const uint32_t* codepoints,
                                          intptr_t length);
 
+DART_EXPORT Dart_Handle Dart_NewExternalString8(

[Anton Muhin, 2011/10/25 10:19:02]

this API might be difficult to use by embedder.  For example, WebCore strings
are refcounted objects and it's difficult (and in some cases impossible) to find
a String object out of content chars pointer.  May we have a second void*
pointer to be passed back into finalizer callback, please?

[cshapiro, 2011/10/25 20:42:47]

Sure, I'll add and additional argument.

+    uint8_t* codepoints,
+    intptr_t length,
+    Dart_ExternalString8Finalizer finalizer);
+DART_EXPORT Dart_Handle Dart_NewExternalString16(

[Anton Muhin, 2011/10/25 10:19:02]

Another note, just in case: ideally we need a way to turn DartVM string into an
externalized one.

[cshapiro, 2011/10/25 20:42:47]

Doesn't the embedding API provide a way to do this by way of the
Dart_StringGet8, Dart_StringGet16 and Dart_StringGet32?

Can you give me an example of when you would need this?

[Anton Muhin, 2011/10/26 14:11:52]

Not quite.  I do not want to fetch a codepoints out of a DartVM string, but
rather turn a DartVM string into externalized one, so later I can perform this
conversion faster.

Use case: we want to get maximum speed out of calls like foo("bar") where "bar"
needs to be converted into embedder's string.  "bar" is DartVM symbol and w/o
ability to turn it into externalized string, embedder will have to convert it on
each invocation.  If embedder can externalize "bar", on subsequent conversions,
(s)he can fetch embedder's sight representation out of "bar" immediately (peer
in your parlance).

v8 achieves it be overwriting string object in the heap.  It's not always
possible (0 length string or even longer one on x64), but works pretty nice.

On 2011/10/25 20:42:47, cshapiro wrote:

[cshapiro, 2011/10/26 23:35:08]

Okay, I think I understand more about what you want...

Obviously, we are doing this a little bit differently from V8.  V8 requires the
embedding application to provide a C++ instance which implement an external
string interface.  This gives the embedder a lot of flexibility as all manner of
functionality can be buried in the class instance.

This API does something different.  We ask for only the data and length at
construction time.  However, we can do something similar to V8.  Instead of
passing a data pointer, we could take 2 arguments at construction time

  1) a vtable-like C structure with function pointers for each logical interface
method
  2) an otherwise opaque instance pointer

To externalize a string, we could require the vtable in 1 to also include a
method to construct an instance of the embedder's choosing and then the VM would
arrange to change the type of the string instance.

It still would be nice, from the perspective of performance, to be able to cache
both the length and data fields in the header of the external string object.  In
your other recent review comment you suggested the data field may not always be
valid.  I would like to understand more about situations when that could happen
to ensure we have the best design.  Could you clarify?

[Anton Muhin, 2011/10/27 14:14:46]

Sorry, I didn't mean data is invalid.  I meant it difficult to find a real owner
of data out of data.

Sorry, I am not sure I remember saying data maybe invalid.  I believe that data
must be immutable and data should be always valid.

Regarding the caching: the only concern is it may make externalized string
object bigger hence making impossible to turn short VM string into an external
one.

On 2011/10/26 23:35:08, cshapiro wrote:

[cshapiro, 2011/10/27 21:12:51]

Thanks for clarifying.  I think we can do what you want although I would like to
have an understanding of what the minimum object size must be.  It is not hard
to imagine cases where large strings benefit from being externalized.  However,
I am wondering how often this is true for shorter strings.

Can we run an experiment to see how often strings of specific lengths are
externalized?  A histogram would be helpful to understand the break-even point.

As an aside, I am not worried about space, even in small strings.  We can always
add an additional indirection to storage outside the object to allows small
strings can be externalized.  At the moment, I am most concerned about getting
the API just right so important use cases are easily accommodated.

[Anton Muhin, 2011/10/31 09:02:04]

I'll run GMail in customized build to gather the stats today/tomorrow.  I would
expect a lot of tiny string as size of the source code in JS is very important
and devs do their best to minimize it.

On 2011/10/27 21:12:51, cshapiro wrote:

[Anton Muhin, 2011/11/01 17:40:44]

Promised data (I collected all the string which can get externalized, not
actually will).  The data after ~1min of corp GMail:

    0:     667 (10.0%)
    1:      17 ( 0.3%)
    2:     293 ( 4.4%)
    3:    2175 (32.7%)
    4:     119 ( 1.8%)
    5:     458 ( 6.9%)
    6:     518 ( 7.8%)
    7:     381 ( 5.7%)
    8:      72 ( 1.1%)
    9:     128 ( 1.9%)
   10:     368 ( 5.5%)
   11:     130 ( 2.0%)
   12:     162 ( 2.4%)
   13:     308 ( 4.6%)
   14:      19 ( 0.3%)
   15:      51 ( 0.8%)
   16:      47 ( 0.7%)
   17:      11 ( 0.2%)
   18:      19 ( 0.3%)
   19:      41 ( 0.6%)
   20:      55 ( 0.8%)
   21:      11 ( 0.2%)
   22:      13 ( 0.2%)
   23:      10 ( 0.2%)
   24:       3 ( 0.0%)
   25:       3 ( 0.0%)
   26:      18 ( 0.3%)
   27:      20 ( 0.3%)
   28:       5 ( 0.1%)
   29:      11 ( 0.2%)
   30:       0 ( 0.0%)
   31:      27 ( 0.4%)
  32+:     496 ( 7.5%)
total:    6656 (100.0%)

On the earlier stages 3chars strings are even more visible:

    0:       0 ( 0.0%)
    1:       8 ( 3.1%)
    2:      54 (21.1%)
    3:     162 (63.3%)
    4:       2 ( 0.8%)
    5:       2 ( 0.8%)
    6:       1 ( 0.4%)
    7:       3 ( 1.2%)
    8:       1 ( 0.4%)
    9:       2 ( 0.8%)
   10:       1 ( 0.4%)
   11:       3 ( 1.2%)
   12:       4 ( 1.6%)
   13:       5 ( 2.0%)
   14:       1 ( 0.4%)
   15:       0 ( 0.0%)
   16:       1 ( 0.4%)
   17:       1 ( 0.4%)
   18:       1 ( 0.4%)
   19:       0 ( 0.0%)
   20:       0 ( 0.0%)
   21:       0 ( 0.0%)
   22:       0 ( 0.0%)
   23:       0 ( 0.0%)
   24:       0 ( 0.0%)
   25:       0 ( 0.0%)
   26:       0 ( 0.0%)
   27:       0 ( 0.0%)
   28:       0 ( 0.0%)
   29:       0 ( 0.0%)
   30:       0 ( 0.0%)
   31:       0 ( 0.0%)
  32+:       4 ( 1.6%)

total:     256 (100.0%)
    0:       1 ( 0.2%)
    1:       8 ( 1.6%)
    2:     102 (19.9%)
    3:     359 (70.1%)
    4:       2 ( 0.4%)
    5:       2 ( 0.4%)
    6:       2 ( 0.4%)
    7:       4 ( 0.8%)
    8:       2 ( 0.4%)
    9:       2 ( 0.4%)
   10:       1 ( 0.2%)
   11:       4 ( 0.8%)
   12:       4 ( 0.8%)
   13:       5 ( 1.0%)
   14:       2 ( 0.4%)
   15:       1 ( 0.2%)
   16:       2 ( 0.4%)
   17:       1 ( 0.2%)
   18:       2 ( 0.4%)
   19:       1 ( 0.2%)
   20:       0 ( 0.0%)
   21:       0 ( 0.0%)
   22:       0 ( 0.0%)
   23:       0 ( 0.0%)
   24:       0 ( 0.0%)
   25:       0 ( 0.0%)
   26:       0 ( 0.0%)
   27:       0 ( 0.0%)
   28:       0 ( 0.0%)
   29:       0 ( 0.0%)
   30:       0 ( 0.0%)
   31:       0 ( 0.0%)
  32+:       5 ( 1.0%)
total:     512 (100.0%)


    0:       1 ( 0.1%)
    1:       8 ( 0.8%)
    2:     103 (10.1%)
    3:     870 (85.0%)
    4:       2 ( 0.2%)
    5:       2 ( 0.2%)
    6:       2 ( 0.2%)
    7:       4 ( 0.4%)
    8:       2 ( 0.2%)
    9:       2 ( 0.2%)
   10:       1 ( 0.1%)
   11:       4 ( 0.4%)
   12:       4 ( 0.4%)
   13:       5 ( 0.5%)
   14:       2 ( 0.2%)
   15:       1 ( 0.1%)
   16:       2 ( 0.2%)
   17:       1 ( 0.1%)
   18:       2 ( 0.2%)
   19:       1 ( 0.1%)
   20:       0 ( 0.0%)
   21:       0 ( 0.0%)
   22:       0 ( 0.0%)
   23:       0 ( 0.0%)
   24:       0 ( 0.0%)
   25:       0 ( 0.0%)
   26:       0 ( 0.0%)
   27:       0 ( 0.0%)
   28:       0 ( 0.0%)
   29:       0 ( 0.0%)
   30:       0 ( 0.0%)
   31:       0 ( 0.0%)
  32+:       5 ( 0.5%)
total:    1024 (100.0%)

I would speculate that most of 3 chars strings are id/classes.  So it looks like
ideally we should be able to externalize strings of 3+ length.

WDYT?


On 2011/10/31 09:02:04, antonmuhin wrote:

+    uint16_t* codepoints,
+    intptr_t length,
+    Dart_ExternalString16Finalizer finalizer);
+DART_EXPORT Dart_Handle Dart_NewExternalString32(
+    uint32_t* codepoints,
+    intptr_t length,
+    Dart_ExternalString32Finalizer finalizer);
+
+
 // The functions below test whether the object is a String and its codepoints
 // all fit into 8 or 16 bits respectively.
 DART_EXPORT bool Dart_IsString8(Dart_Handle object);