-
Notifications
You must be signed in to change notification settings - Fork 205
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Allow objects to be eliminated #306
Comments
I think this should apply to the builder pattern as used by
where the |
That would be great! Please check out #308 and speak up if you see something that you think wouldn't work. ;-) |
Can you elaborate a little bit more on the motivations here? In particular, what is it that you want to enable that is not possible now? A quick check of dart2js output shows that it will eliminate all but one of the object allocations in your example above, and I would be fairly surprised if the VM doesn't do likewise. Test program: import 'dart:core';
void main() {
var now = DateTime.now();
var berlinWallFell = DateTime.utc(1989, 11, 9);
var moonLanding = DateTime.parse("1969-07-20 20:18:04Z");
print(now.isAfter(berlinWallFell));
print(berlinWallFell.isAfter(moonLanding));
var fullString = (StringBuffer()
..write("Use a StringBuffer")
..writeAll(["for ", "efficient ", "string ", "creation "])
..write("if you are ")
..write("building lots of strings"))
.toString();
print(fullString);
} Output when compiled with dart2js: A = {
main: function() {
var moonLanding,
t1 = Date.now(),
t2 = H.Primitives_valueFromDecomposedDate(1989, 11, 9, 0, 0, 0, 0, true);
if (typeof t2 !== "number" || Math.floor(t2) !== t2)
H.throwExpression(H.argumentErrorValue(t2));
moonLanding = P.DateTime_parse("1969-07-20 20:18:04Z");
P.print(t1 > t2);
P.print(t2 > moonLanding._value);
t1 = P.StringBuffer__writeAll("Use a StringBuffer", ["for ", "efficient ", "string ", "creation "], "") + "if you are building lots of strings";
P.print(t1.charCodeAt(0) == 0 ? t1 : t1);
}
}; |
As a language feature "the compiler should generate better code if able" seems really vague. I'd love to allow users to introduce more confidence they are writing explicitly writing optimizable code (whether support constant expressions/functions, something like Kotlin's |
I can see how these optimization opportunities can sometimes be detected today, but the point is that the developer who marks a class as So this marks the class as "intended to be able to evaporate", and hence certain constructor invocations can be eliminated: The object was never created, and its state is stored in local variables (including function parameters). We're essentially storing the object on the stack, and we're free to create as many copies as we want, because the special discipline provides the guarantee that this does not create any difference in the observable behavior. If that is really, seriously no problem to achieve without help then we can just eliminate the notion of static classes from the proposal about how to obtain a generalized version of static extension methods and static extension types in #309. That would just make it simpler. (Note that this amounts to the same thing as saying that we can create wrapper objects to handle extension method invocations at zero cost, compared to a compilation strategy which always just translates the extension methods to static functions.) Otherwise, I believe that the notion of static classes does embody a robust and rather expressive static check on a class which ensures that "non-leaking" (cf. #308) expressions are guaranteed to be transformable into purely static function calls. The core idea is that The only kind of access to the object is member lookup, and that's always a two-step traversal where we have a reference to the object in the middle (to find |
I looked a little bit more closely at the translated code, and several things came to mind.
So I basically remain unconvinced that we already handle the situations where I think object allocations can be avoided, at least not at anything like the same level of generality and predictability that we could have if we were to allow classes to have the modifier I adjusted the examples using main() {
var currentMonth = DateTime.now().month;
var moonLandingDay = DateTime.parse("1969-07-20 20:18:04Z").weekday;
print("Current month: $currentMonth, Moon landing day: $moonLandingDay");
} This translates as follows: ...
main: function() {
var t1 = Date.now(),
t2 = P.DateTime_parse("1969-07-20 20:18:04Z");
H.printString(
"Current month: " +
H.Primitives_getMonth(new P.DateTime(t1, false)) +
", Moon landing day: " + H.Primitives_getWeekday(t2));
}
... So we're still allocating two PS: Interestingly, |
@davidmorgan wrote:
Wouldn't that be Interestingly, we could actually use an extension type (that is, a wrapper class Foo ... {
implicit factory Foo(void Function(FooBuilder) f) {
// We'd do something like this:
FooBuilder fb = ...;
f(fb); // Let the user code set up `fb`.
return fb.build(); // Create and return the corresponding `Foo`.
}
}
main() {
Foo foo = (b) => b..x = 3..y = 4;
} It might seem counter-intuitive to let // Desugared code (`class Foo` is unchanged).
main() {
Foo foo = Foo((b) => b..x = 3..y = 4);
} By the way, if we use the abbreviated function syntax of #265 we can write it like this: main() {
Foo foo = { x = 3; y = 4; };
} This is the same thing, and it desugars the same way, it's just relying on the ability to have a parameter named We rely on type inference to tie the pieces together, because it is only a type correct constructor invocation when inference has decided that the parameter type of the function literal is But given that we've said that we want a However, all this doesn't help much along the way to eliminate any allocations. You wouldn't be in a good position to eliminate the So this is sad, but true—unless the whole thing works differently than I think, it won't be such an obvious use case for static classes after all. But |
I think modifying the class places the decision about whether an instance should be stack-allocated in the wrong place. Wouldn't it be up to the call site to determine that? Example: var foo = &Foo(); // dunno if & is Darty enough
foo.blah();
return bar(foo); Knowing that the value of static Foo _globalFoo;
// The `&` declares that `bar` can take heap- and stack-allocated
// instances of `Foo`. It promises that it will not leak the instance to the
// heap. A static compiler check upholds the promise.
int bar(Foo& foo) {
// _globalFoo = foo; // STATIC COMPILER ERROR
return foo.someField; // OK
} Similar syntax would need to be added for methods, but I can't think of anything Darty. You'd need some way to declare that |
Actually, |
I think we wouldn't want exactly the same amount of complexity in Dart as in Rust, in order to control memory management. The idea behind a static class is that it never leaks |
I think the two sources of complexity in Rust are:
Note that in my suggestion the Where would something like this be useful to me? In UI frameworks you frequently create temporary data structures to compute the minimal delta you want to apply to the UI after the developer told you that something's changed. For example, you may receive two lists (e.g. of widgets) and you want to figure out the minimum amount of edits (add, remove, swap), or you receive a new tree of transform matrices and clips and you want to compute that effective change in the clip. Today we create temporary lists, maps, strings, matrices, rectangles, and other geometric objects on the heap in cases where stack would suffice. Another example is immediately-invoked callbacks, such as void forEach(borrow void f(E element));
// ^
// guarantees that all implementations do not leak `f` |
@yjbanov wrote:
It's certainly an interesting idea, and more powerful than static classes in many ways! But if we allow any references to a stack allocated I don't think it's acceptable for Dart programs to have an even remote risk of seg-faults (that must be a bug in the runtime or in code generation, it can't be caused by a buggy program .. ok, ffi is an exception, but otherwise not), so we will need to maintain that "no dangling pointers" guarantee rigorously, and "the rest of Dart" may not be optimized for establishing such guarantees. What I'm aiming at with static classes is a bit less ambitious. It relies on a stronger discipline whereby it is guaranteed that 100% of the references to a given object can be eliminated, and then we just need to preserve information about which values the would-be object would have in its (final) fields, and which method implementations it would run on a given instance method invocation. My idea is that the methods would be top-level functions, and the object fields would be passed around as parameters of those functions. With that, there's no need to maintain the same memory layout (or even ordering-in-memory) of the variables/parameters which are used to hold the object state, because all accesses to them will be compiled in a context where it is already statically known that they are parameters. Since parameters can be stored in registers, we could then end up having an object that "lives in a few registers" throughout its entire lifetime, so it really never has an address at all. |
That pretty much is the feature request :) The only references to stack allocated objects that would be allowed are ones marked as "borrowed". The language/compiler would have to learn how to make sure that those references are not leaked onto the heap. The interesting question is: what's the minimum sufficient feature set? For example, would we need to support putting borrowed references into borrowed objects, such as class fields and list elements? It is a perfectly safe thing to do (segfault-wise) if the contents are guaranteed to outlive the containing object, but I'm not sure what the simplest way to express it is. Would we need something like Rust's lifetime parameters?
+1 |
@yjbanov wrote:
We might be able to handle such a concept. However, I'm pretty sure that Rust has been optimized for that kind of static proof maintenance almost from day 1, whereas Dart embodies a thousand design decisions that are not optimized in that particular direction, and we might very well have to transform Dart into a kind of a half-Rust-ish language in order to do it. This could mean that every Dart developer would then have to spend a significant amount of brain cycles on getting those "borrowed" bits right. One example is that Dart would presumably need to maintain the stack-allocation related invariants dynamically. We can't prevent dynamic invocations like So I can certainly see the temptation to get the added performance, but I do think that the notion of borrowed objects is so deep that it will have very broad implications for a language to support it, and for developers using it. What I've proposed in terms of 'static classes' (#308) is a much simpler feature: It allows for object allocations to be eliminated in a situation where we have an exact type of an immutable object, and a complete absence of leaking of said object. |
This is a very important point. We should make it a design constraint that this does not happen. I think this can be designed in such a way that does not leak the complexity of borrowing onto developers. For example, this is why I suggested that borrowing functions also allow passing normal heap-allocated objects. What you can do with a borrowed reference should be a strict subset of what you can do with a heap reference. This way the author (and only the author) of the borrowing function opts into this complexity. The author does not opt the users into it as well.
Why not? It seems pretty easy to forbid assigning a
I actually do not see a conflict here. If #308 is useful enough, then by all means, it should be added to the language too. |
Gonna be honest, this sounds a lot like structs... You have "objects" that are just wrappers over plain ol data, and these objects are passed by "copy" by destructuring the inner fields. |
@yjbanov wrote:
That's not where it happens: Consider the situation where we assign an expression of type There may not be a getter
The problem is that |
@ds84182 wrote:
True, but structs (meaning record data types with direct allocation, as opposed to heap allocated entities that are accessed via a pointer) require support from the runtime. So we can't have structs if we translate to JavaScript. But we can compile non-leaking usages of instances of static classes down to a form where that instance is eliminated, also when we translate to JavaScript (or anything whatsoever, because the elimination of that instance is a Dart-level desugaring operation). |
I'm not sure we need borrowed return types. I think these could be disallowed. Alternatively, a borrowed return type may only be assigned to a borrowed variable iff the type of the wrapper object is itself borrowed (not sure if we'd also need lifetimes). Not sure how useful this feature is though. For Rust, this is critical, because there's no GC to fall back on. In Dart there's always GC as the last resort. What would be useful, however, is an ability to construct and return an object along with ownership to the caller (a la C++ move semantics). Again, regular code can be completely oblivious to the fact that ownership is given to them. They can do whatever they want with it (probably leak it onto the heap, and the runtime would happily oblige). However, advanced users should be able to put it on stack and then pass it (lend it?) to functions that borrow the object, avoiding heap allocation. |
@yjbanov wrote:
That's an interesting restriction! We could consider the following rule: A formal parameter p of a function declaration can be given a borrowed type, in which case the body of the function can only contain p in non-leaking positions. This would ensure that we don't need borrowed return types because no expression with a borrowed type can be returned. But unless we restrict this discussion to a setting where we can manage memory ourselves (in particular, not when generating JavaScript), we would need to generate a specialized version of every such function which "accepts the state" of p rather than a regular object (that is, it accepts several formal parameters rather than p), and this would have implications for tear-offs and dynamic invocations etc. And we'd still need to have function types whose parameter types can be borrowed (as well as all other contravariantly positioned types, e.g., the parameter types of a returned function type). So it would still incur a non-trivial language complexity cost. |
Considering borrowed types, here is a description of the kind of red tape that Rust programmers get into if they want to assign one reference to another one: Medium: 'Mutable Reference in Rust'. I think we'd want to be very cautious about forcing Dart programmers into a situation where they need to solve that kind of puzzles. |
I'm not sure how this can be described this way, given that you can continue using the existing language as you do today. The idea is to offer this as an advanced language feature that never "leaks" across API boundaries. That is, non-advanced users should never be exposed to this. The issue with Rust (and other non-GC non-RC languages, like C, C++) is that the language allows this complexity leak out to public API. Consider, for example, the amount of bit-twiddling complexity that goes on in the Dart VM to make strings and ints fast. Does that complexity leak onto the Dart programmer? No. The API looks very natural and "Darty" to use. That should also be a constraint on the feature I'm proposing. |
Is it possible in dart to have non-paused GC like in golang? |
The GC in Dart is concurrent and mostly non-pausing as far as I know. |
Thanks @munificent. Will there be a time in coming years when Dart will be modified to have same performance level(in terms of memory footprint, GC optimization, Lighter isolates etc) as Golang or more performant server side languages. I think that will be a crowd puller to develop the open source server side ecosystem libraries like load balancer, microservice registry, rate limiter etc. Please ignore if my question seems silly. |
This question assumes a premise that it's not already at the same performance as those languages, but that premise requires some sort of agreed-on benchmarks or performance data, and I don't think that consensus exists. There's no context-free way to say language X is faster than Y. Instead it's language X is faster than Y for assumed-equivalent programs Zx and Zy. I think for many programs, Dart is plenty fast enough to be used as a back-end language. (For example, all of our own tools are written in Dart, including the compilers, package manager (both client and server), etc.) |
Are the benchmarks data in following observations qualify for the consensus - https://programming-language-benchmarks.vercel.app/dart-vs-go and https://www.techempower.com/benchmarks/ (I remember seeing Shelf/aqueduct in this but not able to find it anymore. They mention in the git - https://github.com/TechEmpower/FrameworkBenchmarks that they have benchmarked Dart as well - https://github.com/TechEmpower/FrameworkBenchmarks/blob/master/frameworks/Dart/dart2/server.dart). Also once Serverpod will release their throughput benchmarks(serverpod/serverpod#598) probably that will give a better insight and a yardstick to get behind. Thanks for taking out time to reply. |
[Edit: Adjusted
DateTime
examples to create a situation which is directly relevant for a 'static class'.]There are some situations where an object is created in order to hold some data, and some instance methods are invoked on that object in order to compute results or perform actions based on that data. But the object itself is not needed for any other purpose than holding the given data during those method invocations. For instance:
(Examples derived from the DateTime DartDoc and an example in Seth's blog entry on strings in Dart).
If such objects are indeed never needed at all (except as storage locations for the data included in the construction) then we could allow an optimization whereby the allocation of a new object is eliminated, the data is stored in the run-time stack, and the computations are performed in a top-level function.
The text was updated successfully, but these errors were encountered: