Skip to content
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.

Sign up for GitHub

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

Jump to bottom

Rewrite with compressed virtual DOM tree #1

Open
13 of 37 tasks
bakape opened this issue Apr 23, 2019 · 35 comments
Open
13 of 37 tasks

Rewrite with compressed virtual DOM tree #1

bakape opened this issue Apr 23, 2019 · 35 comments
Labels
enhancement

Comments

@bakape
Copy link
Owner

bakape commented Apr 23, 2019 •
edited
Loading

Use as little string allocations as possible and speed up diffs through tokenization:

  • Tokenize all property and tag strings to uint16 IDs and keep in global map.
  • Separate storage field for classes - [ ] most used property. Store as an integer ID pointing to a sorted array of class IDs.
  • Predefine most common HTML tags and properties as constants
    • Have node constructor accept these constants or a string through an Into generic parameter.
  • Have HTML macro use these predefined constants, where possible.
  • Property/tag string storage without extra heap allocations: [1B length][15B string]
    • Fit to 16B for double int alignment
    • Since the type is fixed size, don't derive the Hash trait for it and just return the contents as u64.
    • If string larger than 15B, use fallback String map storage.

Nodes:

  • Implement text nodes as a special kind of <span>, so they stay addressable.
  • Store various node flags in a frontal byte.
  • Function for node data lookup by ID in the patch tree.
  • Method for flagging a node and it's subtree immutable. Such node will never be diffed.
  • Store non-class property values as a hash_map<property_id, String>

Patching:

  • Keep 2 trees - [ ] a DOM state tree and a pending changes tree.
  • Patches are done through either calling a root node insertion function or calling patch functions on node handle.
    • In case of node handle, the node is looked up in the patch tree. Calling patch on an invalid node handle is NOP.
    • Store last found node location as vector of IDs on node handle.
    • A node handle can be generated on any node, by calling a take_handle() method.
    • Node handles are linked to DOM nodes on sync to DOM representation tree.
  • Node handles are the only data type that needs to be a smart pointer.
  • On patch append ID of eldest mutated parent to a set. When subtree of parent is diffed, remove ID from set. If set is empty, diff is complete and can be short circuited.
  • Nodes that have never been taken a handle of can be considered constant and only mutate from parent node patches.
  • Need an append-only data structure that is writable like a string.
    • Contains a vector of buffers.
    • Allocates bigger and bigger buffers as the previous buffer's capacity is exceeded.
    • Each next buffer is twice the size of the previous one.
    • Has a method, that concatenates all the part buffers with only one extra allocation.

DOM events:

  • Node handles are used to declare event handlers.
  • You can build higher level frameworks on top of this.
  • On DOM event fire, check if event type has any registered handlers. If yes, bubble up to the body, collecting brunhild IDs along the way. Descend the DOM representation tree, looking for event handlers as we go. If found, do map lookup against ID and trigger any registered event handles on node handles.

Node creation macros:

  • Macros for element and text node creation.
  • Macros take 1 parameter - dict-like literal, that will be allocated into static memory.
  • Element macro can take 1-2 parameters - 2. is an array of child Nodes.
  • Macro also parses a dict-like attribute list into a slice of tuples, if the parameter is a dict and not a hashmap iterator or similar.

Details:

  • There library takes over the HTML body. Everything to be left untouched must be stored in the <head>.
  • Such tight string and vector storage regions should be good for cache locality
@bakape bakape changed the title Idea: Compress virtual DOM tree Ideas: Compressed virtual DOM tree Apr 23, 2019
@bakape bakape changed the title Ideas: Compressed virtual DOM tree Ideas: Rewrite with compressed virtual DOM tree Apr 23, 2019
@Chiiruno
Copy link
Collaborator

Chiiruno commented Apr 24, 2019 •
edited
Loading

Implement text nodes as a special kind of <span>, so they stay addressable.

Elaborate please. Do you mean a tag or other identifier in the field?

@bakape
Copy link
Owner Author

bakape commented Apr 24, 2019 via email

@Chiiruno
Copy link
Collaborator

Hmm, memory lookup by reference sounds a lot faster, however I'm not considering the cross-FFI penalty.
I don't suppose you could give me a short list of pros and cons for looking up nodes each time by ID, vs a memory reference map/list, could you?

@bakape
Copy link
Owner Author

bakape commented Apr 24, 2019 via email

@Chiiruno
Copy link
Collaborator

The crux here seems to be the user being able to define IDs, and the FFI calls.
Could something like this be of help for massive FFI calls in JS<->WASM, which there shouldn't be a lot of memory sharing to begin with.

@bakape
Copy link
Owner Author

bakape commented Apr 24, 2019 via email

@bakape
Copy link
Owner Author

bakape commented Apr 29, 2019

@Chiiruno

  • Store non-class property values and text node strings inside a global reference-counting map.
    • The map needs to be accessible both by string ID and by actual string.
    • Maybe somehow not allocate a String twice and use references.

Any idea how to implement this map, that both maps strings to IDs and IDs to strings without actually having to allocate the string twice?

@Chiiruno
Copy link
Collaborator

With a map, you can't have the value find the key, right?
Whereas vice versa you can, right?
If the string is the same, you could have a pointer perhaps?

@Chiiruno
Copy link
Collaborator

Chiiruno commented Apr 29, 2019 •
edited
Loading

Oh
Perhaps have the first X characters of the actual string be the string id, have the key be a pointer to the string, and use the first X characters as a key for the string to be found?
Although, you could ditch the map with that.

@bakape
Copy link
Owner Author

bakape commented Apr 29, 2019 via email

@Chiiruno
Copy link
Collaborator

Chiiruno commented Apr 29, 2019 •
edited
Loading

I've had a bad migraine the past few days, so I've just been catching up on manga and listening to quiet music, um... Maybe arc/box for references/pointers?
I'm pretty sure you can make a map with those.
You can also use unsafe to work with raw pointers, while safely storing them in the map.

@Chiiruno
Copy link
Collaborator

Chiiruno commented Apr 29, 2019 •
edited
Loading

With Rust, you could make a type, and set the impl for each location, while having shared ("generic" non-specific) functions higher up in the type I think, I'll have to reread that.

@Chiiruno
Copy link
Collaborator

Trait, I think that might have been it. The type implements trait along with your specific implementation, there may have been a more virtual approach I may be thinking about.

@Chiiruno
Copy link
Collaborator

As for copy operations, for the type you'll want to set it to move instead, I forgot how to do that, but it's easily searchable.

@Chiiruno
Copy link
Collaborator

Never mind, it's move default, and you can add a copy trait if you desire it.
https://doc.rust-lang.org/rust-by-example/trait/derive.html

@bakape
Copy link
Owner Author

bakape commented Apr 29, 2019 via email

@Chiiruno
Copy link
Collaborator

Chiiruno commented Apr 29, 2019 •
edited
Loading

Is there any way to guarantee that we only push to the end of the vector?
I think middle reads are a given here, but we may be able to speed things up by ensuring that we always only push at the end of the vector, to prevent reallocations.

@bakape
Copy link
Owner Author

bakape commented Apr 29, 2019 via email

@Chiiruno
Copy link
Collaborator

As long as the memory usage isn't morbidly high, it should be okay to sacrifice some of it for speed.

@Chiiruno
Copy link
Collaborator

It is important that it fits into the CPU cache though, hm...

@bakape
Copy link
Owner Author

bakape commented Apr 29, 2019 via email

@Chiiruno
Copy link
Collaborator

Assuming an English alphabet, yes.
Common HTML terms and some other terms may be worth the complication.

@Chiiruno
Copy link
Collaborator

You may also be able to compress common non-programming terms in strings down quite a bit with a lookup map, thus saving memory.
However, this assumes English.

@bakape
Copy link
Owner Author

bakape commented Apr 29, 2019 via email

@Chiiruno
Copy link
Collaborator

Yeah, whitelist certain common terms, and maybe words in strings to be compressed.

@bakape
Copy link
Owner Author

bakape commented Apr 29, 2019 via email

@Chiiruno
Copy link
Collaborator

I guess we can't accept a CPU/memory spike on page load to do all of that, since very rarely is someone on the same page for long. The memory usage would be a lot lower assuming they stay on the same page however.
Would there be a way for this to smartly detect pages that are usually active for a long time, or perhaps have a programmer set it?

@bakape
Copy link
Owner Author

bakape commented Apr 29, 2019 via email

@Chiiruno
Copy link
Collaborator

That's fine, but I think it's best to consider the concept now, so less rewriting later.
Of course, avoiding premature optimization.

@bakape
Copy link
Owner Author

bakape commented Apr 29, 2019 •
edited
Loading

  • Need an append-only data structure that is writable like a string.

Could you look work on this one?

@bakape
Copy link
Owner Author

bakape commented Apr 29, 2019 •
edited
Loading

Actually, before that we need to wipe clean and migrate this repo to the newer Rust WASM toolkit.

@Chiiruno
Copy link
Collaborator

Could you look work on this one?

Sure, seems pretty well-defined.

@bakape
Copy link
Owner Author

bakape commented May 6, 2019

@Chiiruno I set up a basic project with wasm_bindgen as the linking layer.

@bakape
Copy link
Owner Author

bakape commented May 6, 2019

String tokenizer done.

@bakape bakape changed the title Ideas: Rewrite with compressed virtual DOM tree Rewrite with compressed virtual DOM tree May 7, 2019
@bakape
Copy link
Owner Author

bakape commented Jun 1, 2019

unsafe unsafe unsafe like grandpa C was intended.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@bakape @Chiiruno