This might be prematur3e optimization, but it seems that on every pixel change, we need to construct a 16x16 list, then diff it. This seems really bad if we ever scale this up to say a 32x32 editor or a 64x64 editor.
Is there a better approach to this ? Formally, the badness is that changing a single pixel in a NxN image now takes NxN work.
I have little context on your app, but I assume, that youâll want to have each position on the grid have a color, and youâd like to not do O(n) work (list creation + diffing + patching) (where n is the number of pixels on-screen) if a single pixel changes its color.
If you can turn your list of children from a color list, into a map of position -> color, and you also update this map incrementally with Map.set, or just donât reconstruct the map from scratch each time, you could get âoptimalâ diffing + ânot needing to create an O(n) list on each updateâ, by using Vdom_node_with_map_children. Theyâll be placed in the order according of the mapâs comparison function, so your âpositionâ type could even be a record {y:int; x:int}, if the compare function puts them in the right spot, but the âpositionâ type could also be an int thatâs the âflattened indexâ of the grid.
It is important to note that not âreconstructing the map from scratchâ is important, (e.g. only updating it with Map.set, incrementally mapping/folding it with Bonsai.assoc/Bonsai.Map.* functions. An example of something sad would be accidentally doing Map.map instead of assoc which would reconstruct the map)
This sadness is due to an implementation detail of the library. Namely, it uses Map.symmetric_diff to be able to diff the two maps efficiently, and the implementation of symmetric_diff relies on phys_equal / âsame addressâ/ âsame tree nodes in the mapâ equality to be able to do diff the map really in less than O(n) time by doing early cutoffs.
Thanks. This sounds like the 2nd (or third) time lack of mastery of this âMapâ is my problem.
i have a question here about map: In the list approach, because the child divs are ordered, if I want to set the color of row R, column C, I can set it at item (R * 16 + C) of the list.
I understand that in a standard red-black / avl tree map, the children are âorderedâ in the tree. Thatâs not my question here. In the corresponding Vdom.Node.t , are the children (div) there ordered ? If so, how are they ordered ? If not, do we need to do css magic to ensure that each âchild/cellâ draws itself to the right place ?
Good question! They are ordered according to the order of Map.data (which is the order of the âcomparison function of the mapâ (This is explained at the end of this answer)). The order of Map.data is the order of List.sort ~compare (key_star_value_list : (key * value) list) where compare compares the keys of the map.
Vdom.Node.div (Map.data map)
should have the same order as:
Vdom_node_with_map_children.make ~tag:"div" map
, but does not actually call O(n)Map.data, and does something faster in its implementation with symmetric_diff.
By âorder of the comparison function of the mapâ, I am referring to a convention from the Core library.
If you want to make a map of your own âcoordinateâ type, you need to do an awkward dance like:
module Coordinate = struct
module T = struct
type t =
{ y : int
; x : int
}
[@@deriving sexp]
let compare =
Comparable.lexicographic
[ Comparable.lift Int.ascending ~f:(fun t -> t.y)
; Comparable.lift Int.ascending ~f:(fun t -> t.x)
]
;;
end
include T
include Comparable.Make (T)
end
where the compare function you implement specifies the order in the map. In this case, I wrote it such that âyâ is compared first, and then if y is equal, it compares against x via helper functions from Comparable. (assuming that your top-left pixel is {y = 0; x = 0}, and y decreases downwards, and x increases rightwards)
You could also use ppx_compare to do this in a way thatâs less verbose (the subtly being that since y appears before x in the type definition, itâll compare y first and then x):
module Coordinate = struct
module T = struct
type t =
{ y : int
; x : int
}
- [@@deriving sexp]
+ [@@deriving sexp, compare]
- let compare =
- Comparable.lexicographic
- [ Comparable.lift Int.ascending ~f:(fun t -> t.y)
- ; Comparable.lift Int.ascending ~f:(fun t -> t.x)
- ]
- ;;
end
include T
include Comparable.Make (T)
end
I apologize if you have explained this before and I failed to understand it then. I feel like Bonsai is using âmultiple layers of magicâ and Iâm unwrapping it layer by layer.
val make : tag:string -> ?attr:Vdom.Attr.t -> (_, Vdom.Node.t, _) Map.t -> Vdom.Node.t
This Map.t here is just a regular Core Map.t right ?
An immediate followup here is: how do we do Sub O(n) diffs ? Suppose again, we have a NxN image. In âdestructive JSâ, to update a pixel/cell, we do O(1) work in JS; then who knows how much work the Browser/DOM does, but our JS code only does O(1) work â it finds the div, and changes the color. And if we do K updates, the JS does O(K) work.
Here K = number of pixels changed. S = dimension of square image. N = S * S = ttl pixels.
In the âBonsai Listâ solution suggested, if we do K updates, it is O(K * S * S) work. In the âBonsai Mapâ solution you are suggesting, it is O(K * log(S * S)) = O(K * log S) work right ? A balanced tree has depth O(log S).
The way we pull off this O(log N) diff â is this via Chris Osaki / Persistent Data Structures?
Naively, suppose we have old_map, new_map, and they differ in at most k entries.
In the naive case, if we have no extra info, we have to do O(N) work to find the diff between them.
Suppose however, new_map is derived from old_map via K EDIT_OPS, and each EDIT_OP uses structural sharing (as persistent data structures do), where we have the guarantee:
This means that we can ârecover the diffâ in O(k * log N) time instead of O(N) time,
This of course, requires that new_map be derived from old_map via a series of EDIT-OPs that satisfies [eq 1].
Is the above the core of what you are getting at with:
This sadness is due to an implementation detail of the library. Namely, it uses Map.symmetric_diff to be able to diff the two maps efficiently, and the implementation of symmetric_diff relies on phys_equal / âsame addressâ/ âsame tree nodes in the mapâ equality to be able to do diff the map really in less than O(n) time by doing early cutoffs.
In addition to previous questions, one thing I am really curious now is how exactly does:
Vdom_node_with_map_children.make
work
It has the following type signature:
val make : tag:string -> ?attr:Vdom.Attr.t -> (_, Vdom.Node.t, _) Map.t -> Vdom.Node.t
It has this impl:
(* js-only: The instancer is a weak-map from comparator objects to a widget-implemented vdom
function. This is so that each kind of map will get its own widget for safe diffing.
The implementation of this function is quite scary, no doubt, but Carl claims that
physical-equality of comparator objects is proof that the key and comparator_witness
types are guaranteed to be equal *)
module Instancer : sig
val get : map:('k, Vdom.Node.t, 'cmp) Map.t -> ('k, 'cmp) Input.t -> Vdom.Node.t
end = struct
module Weak_map = Jsoo_weak_collections.Weak_map
let instances : (Obj.t, Obj.t) Weak_map.t = Weak_map.create ()
let get (type k cmp) ~(map : (k, Vdom.Node.t, cmp) Map.t)
: (k, cmp) Input.t -> Vdom.Node.t
=
let key = (Obj.repr : _ Core.Comparator.t -> Obj.t) (Map.comparator map) in
match Weak_map.get instances key with
| Some i -> (Obj.obj : Obj.t -> (k, cmp) Input.t -> Vdom.Node.t) i
| None ->
let module M =
Widget (struct
include (val Map.comparator_s map)
end)
in
let f = unstage (Vdom.Node.widget_of_module (module M)) in
Weak_map.set instances key ((Obj.repr : (_ Input.t -> Vdom.Node.t) -> Obj.t) f);
f
;;
end
let make ~tag ?attr children =
let f = Instancer.get ~map:children in
f { Input.children; tag; attr }
;;
Here is my confusion:
That function can NOT literally construct a Vdom.Node.t right? Doing so alone would be O(n) time. The only way this could possibly work is that this function, instead of being stateless outputting a Vdom.Node.t, it must somehow:
3.1 store the old value old_map
3.2 store the new value new_map
3.3 do a diff of the two in O(k * log N) time to get the diff, without fully instantiating the new_dom alone (that would be O(N))
This makes me wonder: is there some type of a lazy type in Vdom.Node.t ? Where instead of actually producing a literal Vdom.Node.t with fully instantiated nodes, Vdom_node_with_map_childen.make outputs a Vdom.Node.t that has some type of âLAZYâ node that is passed to the vdom diff-er, and that diff-er computes a diff w/o fully constructing both trees?
I.e. given âlazy old_tree; lazy new_tree; old_treeâ it computes a diff to take old_tree to new_tree without first fully constructing ânew_treeâ (if this makes sense at all).
This might be easier than I thought. Is a âfastâ solution merely:
module Coordinate = struct
module T = struct
type t = {
y: int
; x: int
} [@@deriving sexp]
;;
let compare =
Comparable.lexicographic [
Comparable.lift Int.ascending ~f:(fun t -> t.y)
; Comparable.lift Int.ascending ~f:(fun t -> t.x)
] ;;
end
include T
include Comparable.Make (T)
end
module Texture_8_8 = struct
type t = {
data: (Coordinate.t, Vdom.Node.t, Coordinate.comparator_witness) Map.t
};;
let default: t = {
data = Map.of_alist_exn (module Coordinate) @@
List.concat @@ List.init 8 ~f:(fun row ->
List.init 8 ~f:(fun col ->
( Coordinate.{ y = row; x = col } , Vdom.Node.div ~attrs:[Vdom.Attr.class_ "texture_cell"] [ ] )
)
)
};;
end
let texture_grid (texture: Texture_8_8.t) : Vdom.Node.t Computation.t =
Bonsai.const @@
Vdom_node_with_map_children.make ~tag:"div" ~attr:(Vdom.Attr.class_ "texture_grid") texture.data
;;
By âfastâ here, we mean that changing a pixel results in: O(log n) work for computing diff, O(1) work for updating DOM.
We eat the O(log n) slowdown because in general, when going from imperative / destructive-update algo to pure/functional updates, there is a O(log n) slowdown in general.
Good questions! Iâll attempt to answer them one by one, and also happy to answer follow ups after that.
Yup! Itâs any map from Core.
Yup! Youâve answered the question to the second question with your third question. I have not fully read Chris Osakiâs work/nor am I well versed in Persistent Data Structures, but it is my understanding that coreâs maps are implemented on top of AVL treeâs, where if you only change a single entry in the map/tree, a majority of the tree will remain structurally equal. This is not quite as good as getting a diff of a single element in O(1), but instead O(logn) for a single element as you mentioned.
Yup! I agree with what you are saying. Sorry for the lack of explanation/details in my first answers >.>
The implementation is a bit complex, but the key bits are the call to symmetric diff, and the direct dom mutation based off of the symmetric diff.The other piece of magic - is an implementation detail - the âwidget apiâ that lets you do âdom mutating stuffâ from within bonsai. The code you pointed at is just a cache around the widget api so that if you call it from a Int.Map.t, you get a different âWidgetâ from if you called it from a String.Map.t. To my knowledge, there are no lazy vdom nodes. The implementation sort of âbypassesâ the Vdom.Node.diff that occurs at the top level of every bonsai application and instead does it at the level of the widget, so the map never gets passed to the vdom differ.
I took a stab at implementing a mock pixel editor here. (warning the bundled JS is 6MB, so please donât click if youâre on a data plan). Its source lives in a single file here if it helps for referencing. Interestingly, most of the time is spent painting and recomputing styles on a 200x200 grid (compared to a small part on running javascript), so I wonder if maybe using a non-flat html structure, maybe splitting it off row-by-row and using smaller maps could make things quicker, although I really have no idea without experimenting >.>
module Texture_8_8 = struct
type t = {
data: (Coordinate.t, Vdom.Node.t, Coordinate.comparator_witness) Map.t
};;
let default: t = {
data = Map.of_alist_exn (module Coordinate) @@
List.concat @@ List.init 8 ~f:(fun row ->
List.init 8 ~f:(fun col ->
( Coordinate.{ y = row; x = col } ,
Vdom.Node.create "rect" ~attrs:[
Vdom.Attr.class_ "svg_texture_cell"
; Vdom.Attr.create "x" [%string "%{(col*20)#Int}"]
; Vdom.Attr.create "y" [%string "%{(row*20)#Int}"]
] []
(*
Vdom.Node.div ~attrs:[Vdom.Attr.class_ "texture_cell"] [ ]
*)
)
)
)
};;
end
let texture_grid (texture: Texture_8_8.t) : Vdom.Node.t Computation.t =
Bonsai.const @@
Vdom_node_with_map_children.make ~tag:"svg" ~attr:(Vdom.Attr.class_ "svg_texture_grid") texture.data
;;
and it appears I am getting a bunch of divs rather than svg nodes.
The XY problem here is: in addition to building a âpoor manâs pixel editorâ; Iâm also interested in using the same code to goof around on a âpoor manâs svg editorâ; but it appears to me right now vdom_with_map_children is hard coded to div nodes ?
Iâm not sure if there is a 1 line fix or if I am setting future me up for unimaginable debugging fun, but it appears a 1-line âfixâ adds support for svg:
val update : prev_input:input -> input -> state -> element Js.t -> element Js.t
I am going to label it as
val update :
old_map: input ->
new_map: input ->
state ->
cur_dom_parent: element Js.t ->
return_value_new_parent: element Js.t
In this particular situation here, we have input = T = ('key, Vdom.Node.t, _) Map
As you have linked, we call diff on old_map and new_map, then we compute new parent from old parent.
So I think the running time analysis looks something like:
5.1: going from data â Vdom.Node.t : this takes O(1) since we just take the new map, wrap it in a widget
5.2 virtual dom diff: for this particular part, it does work O(1) + whatever work Widget::update does
5.3 Widget::update computes the diff of old_map / new_map â and assuming we are careful in construction of new_map, this takes O(k * log N) time
5.4 then we build new element Js.t from old element Js.t and this takes O(k) + whatever time Browser uses for DOM updates
Thanks for your patience. I think I finally have a mental model of the gist of how Vdom_node_with_map_children works. Are the above assumptions correct ?
I have some questions regarding Bonsai.assoc. The type signature is:
(** [assoc] is used to apply a Bonsai computation to each element of a map. This function
signature is very similar to [Map.mapi] or [Incr_map.mapi'], and for good reason!
It is doing the same thing (taking a map and a function and returning a new map with
the function applied to every key-value pair), but this function does it with the
Bonsai values, which means that the computation is done incrementally and also
maintains a state machine for every key-value pair. *)
val assoc
: ('key, 'cmp) comparator
-> ('key, 'data, 'cmp) Map.t Value.t
-> f:('key Value.t -> 'data Value.t -> 'result Computation.t)
-> ('key, 'result, 'cmp) Map.t Computation.t
This seems really bad, because our updates becomes O(N) insteacd of O(log N)
if yes:
What is happening here? Does this mean that f is NOT called on every (key, value) pair of the new map ? I.e. the internals is:
get diff of old, new
only call f on (k,v) pairs of the diff // â main diff of Bonsai.assoc vs Map.map ?
patch the result in the ('key, 'result, 'cmp) Computation.t
i.e. we would require that f be pure function (canât even rely on randomness) and have no side effects (definitely canât rely on f being called on every (k, v) pair)
Is this an approximately correct understanding of Bonsai.assoc ?
Oh neat! your solution sounds reasonable. To get extra assurance that your solution behaves the same under all circumstances, you could copy+edit the test suite that tests that Vdom_node_with_map_children behaves correctly. It runs 4 ways of doing the âsameâ thing, creates some randomized sequence of inputs, runs them, and asserts that the vdom nodes are in the right spot at each step of the sequence. Sadly, due to it testing interactions with the browser, it does need to be manually run on the browser/does not run when you run duneâs tests.
To the best of my knowledge, I think they are correct. I am a bit unsure what the time complexity of browser interactions like insertBefore are. One possible extra step is that when create gets called (When the Vdom.Node.t is first mounted onto the html dom) it takes O(n) time as it wonât have anything else to diff before/uses Map.data.
The answer to your previous question is yes. A simpler function than assoc is Incr_map.map. Its implementation lives here and is basically the algorithm you described. The main difference is that assoc is more powerful as the ~f function can itself contain an incremental computation for each element. assoc is more similar (and implemented on top of!) Incr_map.mapi'. This does come at a cost though (mapi' needs more bookkeeping) than Incr_map.map, so bonsai has an optimization pass where - if possible - itâll use Incr_map.mapi instead of Incr_map.mapi'.
(Sorry for my delayed response on this! Also happy to answer follow up questions!)