Comments (9)
Are you sure that this is not something the compiler already optimizes way? I have a hunch that it could, and if it doesn’t, that it should :-)
from motoko-base.
It doesn't seem so. According to my measurements it saves 24 bytes per node of that form (each #leaf costs 12 bytes and it doesn't get optimized away).
from motoko-base.
This other, more efficient representation that is mentioned in the comments of RBTree.mo would benefit just the same:
// TODO: a faster, more compact and less indirect representation would be:
// type Tree<K, V> = {
// #red : (Tree<K, V>, K, V, Tree<K, V>);
// #black : (Tree<K, V>, K, V, Tree<K, V>);
// #leaf
//};
from motoko-base.
As Joachim says, singleton typed objects (such as #leaf ()
) should end up on the static heap and not on the dynamic one. Can you wasm2wat
your file and paste here a short function (or snippet) that allocates a #leaf
dynamically?
from motoko-base.
I am running
actor {
type Color = { #R; #B };
type Tree = {
#node : (Color, Tree, Nat, Tree);
#leaf
};
let l : Tree = #leaf;
let a = Prim.rts_heap_size();
let t1 : Tree = #node (#R, #leaf, 0, #leaf);
let b = Prim.rts_heap_size();
let t2 : Tree = #node (#R, l, 0, l);
let c = Prim.rts_heap_size();
Debug.print("Tree1 : " # debug_show (b - a));
Debug.print("Tree2 : " # debug_show (c - b));
}
with output
[Canister uwugh-uaaaa-aaaaa-aaa5q-cai] Tree1 : 72
[Canister uwugh-uaaaa-aaaaa-aaa5q-cai] Tree2 : 48
from motoko-base.
Bug is confirmed:
For this program
$ cat tree.mo
type Tree = {#leaf; #node : (Tree, Tree) };
func leaf() : Tree = #leaf;
func node(l : Tree, r : Tree) : Tree = #node (l, r);
ignore node(leaf(), leaf());
I get allocations for #leaf
:-(
(func $leaf (type 16) (param $clos i32) (result i32)
(local $heap_object i32)
i32.const 3
call 142
local.tee $heap_object
i32.const 15
i32.store offset=1
local.get $heap_object
i32.const 1202717598
i32.store offset=5
local.get $heap_object
i32.const 0
i32.store offset=9
local.get $heap_object)
from motoko-base.
Can you open an issue in the motoko repo?
ir_passes/const.ml
misses a case for PrimE (TagPrim, es)
and then in codegen/compile.ml
the module Const
and compile_const_exp
needs to learn about constant variants.
I don’t recall a reason why we don't have it already, probably just oversight.
Maybe do OptPrim
while we are at it. Do you want to do it, or should I do it once I get around to it?
from motoko-base.
I am working on a patch. See dfinity/motoko#3878.
from motoko-base.
A compiler patch will fix the same for the Color
as #R
and #B
will become static, too.
After the patch, what will be the most compact representation for a node in RBTree?
Ignoring the K-V pair, we have (current type)
type Color = { #R; #B };
type Tree = {
#node : (Color, Tree, Tree);
#leaf
};
at 32 bytes per #node.
Proposed type (as per comment in RBTree.mo)
type Tree = {
#red : (Tree, Tree);
#black : (Tree, Tree);
#leaf
};
at 28 bytes per #red/#black.
But the most compact would be
type Tree = (Color, ?Tree, ?Tree);
at 20 bytes.
from motoko-base.
Related Issues (20)
- Chore: rename/factor RBTree unshare tests to avoid confusion.
- chore: delete antora related doc detritus
- Float.equalWithin tolerance?
- Doc: add link to doc site to readme
- Add messageQueueLeft() method to ExperimentalInternetComputer HOT 2
- The term "bets" is introduced without first explaining what it means HOT 9
- Error propagation in CI is broken HOT 1
- Deque.size() is missing
- Stack overflow for Heap.fromIter
- AssocList is missing keys(), vals()
- bug: undocumented functions
- Class `SHA224` in `Principal.mo` contains dead data HOT 1
- Array.chain(): Error "index out of bounds"
- Principal.mo uses deprecated function HOT 5
- sequence-like collections should have a `group` operation that lumps together equal subsequences
- utilities for tuple comparisons
- FR: consider adding List.contains : (List<A>, A, (A,A) -> Bool) -> Bool (or similar)
- FR: consider adding module `VarArray` with mutable versions of the immutable array functions in `Array`
- chore: test `viper` again
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from motoko-base.