1107364 - move findNodeByDetails to treeView.js and make it use an hash

Status: RESOLVED FIXED

(Firefox :: Bookmarks & History, defect, P2)

Comment 1

[Marco Bonardo [:mak]]

yep, the current situation doesn't make any sense...

Comment 2

[Asaf Romano (gone)]

FWIW it did make sense back then, when the tree view implementation was coupled with results (not that this did make sense, of course, but that's the reason we've got here).

Comment 3

[Marco Bonardo [:mak]]

This would be very useful from a perf point of view.

What we need to to here is removing FindNodeByDetails from nsNavHistoryContainerResultNode and  nsINavHistoryResultNode, and reimplement it in browser/components/places/content/treeView.js.

In the js version, instead of linearly walking all the containers recursively, we should instead create a Map between node details (the key could be a combination of itemId, url and time) and tree row index. The challenge here is to keep the Map up-to-date with the tree. the points where we already update the _rows array could be a good starting point for that.

Comment 4

[J M]

I'm planning to submit a patch for this bug as part of an assignment for CSC302 at the University of Toronto.

Comment 5

[Marco Bonardo [:mak]]

oh nice, thank you. Let me know if you need help starting up with Firefox development or you already have all the environment setup according to the documentation.

Comment 6

[J M]

Will do. I've got the environment set up and I think I have a pretty good grasp of things, but I'll let you know if I have any questions. Thanks!

Comment 7

[Amila indrajith]

Hi Jonathan,

Are you still working on this bug? If you are not I would like to work on this.

Comment 8

[J M]

Hi Amila,

I'm no longer working on this. Please feel free to take it.

Comment 9

[Amila indrajith]

Hi,
I'm going to try this bug.I'm new to these open source projects.
I find out those things in the code but I don't have much idea about those nsNavHistoryContainerResultNode and  nsINavHistoryResultNode .
can someone guide me here?

Comment 10

[Marco Bonardo [:mak]]

(In reply to Amila indrajith from comment #9)
> Hi,
> I'm going to try this bug.I'm new to these open source projects.
> I find out those things in the code but I don't have much idea about those
> nsNavHistoryContainerResultNode and  nsINavHistoryResultNode .
> can someone guide me here?

The former is a Class, it's defined in nsNavHistoryResult.cpp/h
The latter is an interface, implemented by the above class and it's defined in nsNavHistoryService.idl
What's the question specifically?

Comment 11

[Horatiu Lazu]

Hi, I would like to work on this bug. Is that possible?

Comment 12

[Marco Bonardo [:mak]]

Sure, the easy part here is the conversion from cpp to js, the hardest part may be to build the hash map. so it could be done in 2 separate patches.

Comment 13

[Marco Bonardo [:mak]]

while this is mentored, it's not a [good first bug]

Comment 14

[Horatiu Lazu]

Hi, how would I know if I'm doing this right - the history should work in Firefox? I'm a bit confused about what this code does in the greater context of Firefox. Thanks!

Comment 15

[Marco Bonardo [:mak]]

I'm not sure I got the question, but yes, this code is used by history treeviews in Firefox.

Comment 16

[Horatiu Lazu]

Hi. I took a look at the code a bit, and I have a few questions. Firstly, where is the findNodeByDetails called? It seems like it's mentioned in the interfaces (which I would need to remove), and then in PTV__getNewRowForRemovedNode within TreeView.js - is this correct? It sounds wrong and it seems like it'd need to be called in more places. Secondly, I added some debug code on my own and it seems like findNodeByDetails gets called everytime a row gets clicked on in the history treeview. Is this correct? Thanks in advance, I'm just trying to grasp the code a bit, seems like a lot to learn.

Comment 17

[Marco Bonardo [:mak]]

(In reply to Horatiu Lazu from comment #16)
> Hi. I took a look at the code a bit, and I have a few questions. Firstly,
> where is the findNodeByDetails called? It seems like it's mentioned in the
> interfaces (which I would need to remove), and then in
> PTV__getNewRowForRemovedNode within TreeView.js - is this correct? It sounds
> wrong and it seems like it'd need to be called in more places.

No, it's only invoked there. The treeview hits this hot path when removing nodes, and that makes any removal very expensive.

Secondly, I
> added some debug code on my own and it seems like findNodeByDetails gets
> called everytime a row gets clicked on in the history treeview. Is this
> correct?

It shouldn't, but it's possible if the click causes an invalidate call, that invokes _restoreSelection.
You can get a stack if you set a breakpoint in the debugger on that method and then use DumpJSStack() (see http://www-archive.mozilla.org/scriptable/javascript-stack-dumper.html and https://developer.mozilla.org/en-US/docs/Mozilla/Debugging/Debugging_Mozilla_with_gdb)
Or from js you can either use the Browser Toolbox debugger or dump the value of "new Error().stack"

Comment 18

[Horatiu Lazu]

Thank you very much! Everything makes much more sense now. Last question (hopefully), for mChildren, in FindNodeByDetails (C++), is there an easy way to access something equivalent in JS? I tried for a while to access the children of the container but that didn't work. I also tried this._rows but didn't seem right either, as it just gave me the containers. Thank you.

Comment 19

[Marco Bonardo [:mak]]

(In reply to Horatiu Lazu from comment #18)
> Thank you very much! Everything makes much more sense now. Last question
> (hopefully), for mChildren, in FindNodeByDetails (C++), is there an easy way
> to access something equivalent in JS? I tried for a while to access the
> children of the container but that didn't work. I also tried this._rows but
> didn't seem right either, as it just gave me the containers. Thank you.

The idea from javascript is to create a Map when nodes are added to the view (and keep the map up-to-date when nodes are removed/moved, so every time the view changes) so you should not need to access the whole list of children, you should just need to create a unique key based on uri-time-itemid and query the Map through it to get the node (or even better directly get the row number).
Fwiw, currently in treeview.js there's a _rows property that contains an array of all the nodes, so it should be possible to replicate the current behavior through it (but it would be really slow without a Map cause you should again walk the whole array).

Comment 20

[(no longer active)]

It would be nice if someone can take some measurements from this function, its hard for me to judge how much this can be improved and how slow it currently can be.

Comment 21

[Marco Bonardo [:mak]]

(In reply to :Ehsan Akhgari (super long backlog, slow to respond) from comment #20)
> It would be nice if someone can take some measurements from this function,
> its hard for me to judge how much this can be improved and how slow it
> currently can be.

It's currently an O(n), basically for every change we have to linearly walk the whole tree. Now imagine that on a tree like the history sidebar or a very large bookmarks folder.
In addition to this, our notifications are not so efficient at the moment (bug 1340498) that means in some cases we repeat that linear search multiple times in a row.
In general when this happens the browser hangs for many seconds.

Comment 22

[Milind L (:milindl)]

Attachment: Bug 1107364 - remove findNodeByDetails and maintain a map to fetch a node by details speedily,

This patch removes the interface/header/implementation if `findNodeByDetails` and
replaces it by a map [{uri, itemId, time} -> Node] which can recover a node speedily
by details.

Review commit: https://reviewboard.mozilla.org/r/144002/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/144002/

Comment 23

[Milind L (:milindl)]

I'd like to work on this. I made a patch, please check it out.

Currently, I made the map from nodeDetails -> node, not nodeDetails -> rowNum. I can switch to the values being row numbers instead of nodes if needed.

The nodeDetails are represented as a string, and I have made a function to make that string. Tell me if there are any better ways to represent them (some kind of a standardized way would be good here, I'm using an arbitrary format).
 
I am able to delete stuff in small (1-100) quantities from the treeView (I have not timed, I simply did it to see if it worked). Putting debug code in shows me that indeed while we access the map inside getNew..., it does return a node.

I hope I am going about this the right way, and maintaining the map correctly.

Thanks!

Comment 24

[Marco Bonardo [:mak]]

(In reply to Milind L (:milindl) from comment #23)
> Currently, I made the map from nodeDetails -> node, not nodeDetails ->
> rowNum. I can switch to the values being row numbers instead of nodes if
> needed.

I think the only consumer of findNodeByDetails immediately invokes this._getRowForNode(newNode, true);
So it sounded like a good idea to just track row numbers instead of nodes. Mapping a number may also be cheaper.
But _getRowForNode contains enough complication that we could probably delay the change for safety, if that helps.
Regardless, we are unlikely to land this before the next merge (13th of June), it's a regression-prone change.

> The nodeDetails are represented as a string, and I have made a function to
> make that string. Tell me if there are any better ways to represent them
> (some kind of a standardized way would be good here, I'm using an arbitrary
> format).

I think a custom format will do, we should try to keep it small, it doesn't have to be human-readable since it's not for our consumption, I'd just join the values with a separator char in the middle.

> I hope I am going about this the right way, and maintaining the map
> correctly.

Please check the nodeHistoryDetailsChanged notification, you may have to replace an entry in the Map if time changes, and that may not be trivial. At first glance looks like we may need an inverse Map... but I don't think that itemId and uri can change, thus I'm wondering if we could rather change NodeHistoryDetailsChanged to return both old and new values, then we could find a key using the old value.
Actually, I'm not even sure why NodeHistoryDetailsChanged passes out the new values as arguments, since it also passes the node that already has the new values. It should pass out the updated node AND the old values... Maybe we should do this in a bug apart that blocks this bug, that should be mostly safe to do (I assume).

Sorry if I'm a bit vague, this bug requires more brainstorming than usual since the idea is clear but the implementation details are totally not written down.

Comment 25

[Marco Bonardo [:mak]]

Comment on attachment 8872473 [details]
Bug 1107364 - remove findNodeByDetails and maintain a map to fetch a node by details speedily,

This needs to be updated per the dependency bug, so clearing for now.

Comment 26

[Milind L (:milindl)]

> I think the only consumer of findNodeByDetails immediately invokes
> this._getRowForNode(newNode, true);
> So it sounded like a good idea to just track row numbers instead of nodes.
> Mapping a number may also be cheaper.

The original thought behind this was the times that we have spliced the _rows array. In that case the indices of a lot of the elements change, and so it may be expensive to remap all that. For example, `this._rows.splice(row, 0, aNode)` would affect all indices in _rows after `row`. In this case I would need to remap each of those nodes.

Comment 27

[Milind L (:milindl)]

Ok, I put in a few console.log(...) statements each time we splice, and the #elements we may need to replace in the Map for that splice, and it seems like every time we delete a single item from the history, we might need to splice a large number of elements. I was working with around 70 history items, and the number of elements that I needed to splice while deleting seemed like they could be till 70 depending on the row I chose to delete.

Comment 28

[Marco Bonardo [:mak]]

Ok, thanks for checking, let's move on with the current approach, I'll try to find some time to brainstorm in the next days.

Comment 29

[Milind L (:milindl)]

Comment on attachment 8872473 [details]
Bug 1107364 - remove findNodeByDetails and maintain a map to fetch a node by details speedily,

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/144002/diff/1-2/

Comment 30

[Milind L (:milindl)]

> Bug 1107364 - remove findNodeByDetails and maintain a map to fetch a node by
> details speedily,
> 
> Review request updated; see interdiff:
> https://reviewboard.mozilla.org/r/144002/diff/1-2/

The good thing about this patch - seems to work, when I tested locally with some debug code (comparing `this._rows` and the map I created).

up for ideas/suggestions/potential problems:
 - creation of a `NodeDetails` object - I can probably do without, and try to use just a Map, but some code, especially `replaceNode` is a few lines and is repeated a lot of times, and calling `keyForNodeOrDetails` for each map accessing function also seemed tiresome.
 - Mapping to nodes vs mapping to row numbers
 - need to be especially careful (I think) about the fact that a node should not stay in the map any longer than it needs to. In the usage I did locally, it doesn't seem to be a problem but may be one if I have made some mistakes.

Thanks!

Comment 31

[Marco Bonardo [:mak]]

Comment on attachment 8872473 [details]
Bug 1107364 - remove findNodeByDetails and maintain a map to fetch a node by details speedily,

https://reviewboard.mozilla.org/r/144002/#review156682

I just tested it, it seems to work fine, and we are at the beginning of the 56 cycle, so it sounds like a good time to land this and get feedback, we should have time to look into eventual regressions.

::: browser/components/places/content/treeView.js:30
(Diff revision 2)
> +
> +/**
> + * A handy object to maintain a map and take care of any operations we might
> + * need to do repeatedly.
> + */
> +function NodeDetails() {

I'm not extremely convinced of the need for this Map abstraction. The only things that it seems to add are an helper to create keys (that could still exist without it, just with a shorter name like makeNodeDetailsKey()) and a replace() method, that could be easily replaced by delete+set (Also because when you have a replace method, there's often the doubt of what of the 2 arguments is the new one).

Indeed, I was about to suggest to just name the methods after the Map methods, and I soon realized the additions were not many.

Does this exist to support future changes built on top of it? Since otherwise looks like we could just put a nice comment above this._nodeDetails with a sum up of the comments here and be done with it.

Comment 32

[Milind L (:milindl)]

Comment on attachment 8872473 [details]
Bug 1107364 - remove findNodeByDetails and maintain a map to fetch a node by details speedily,

https://reviewboard.mozilla.org/r/144002/#review156682

> I'm not extremely convinced of the need for this Map abstraction. The only things that it seems to add are an helper to create keys (that could still exist without it, just with a shorter name like makeNodeDetailsKey()) and a replace() method, that could be easily replaced by delete+set (Also because when you have a replace method, there's often the doubt of what of the 2 arguments is the new one).
> 
> Indeed, I was about to suggest to just name the methods after the Map methods, and I soon realized the additions were not many.
> 
> Does this exist to support future changes built on top of it? Since otherwise looks like we could just put a nice comment above this._nodeDetails with a sum up of the comments here and be done with it.

yes, I wasn't too sure of it myself actually (it seemed somewhat overkill)
Basic logic behind creation was that I was composing two functions repeatedly(map methods + key making) and the fact that in this particular map, the keys and the values are related, so I thought it was sensible to not to pass 2 but just one parameter, since first one could be made from the second

In any case, I will shortly submit a patch with your suggested changes.

Comment 33

[Milind L (:milindl)]

Comment on attachment 8872473 [details]
Bug 1107364 - remove findNodeByDetails and maintain a map to fetch a node by details speedily,

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/144002/diff/2-3/

Comment 34

[Marco Bonardo [:mak]]

Comment on attachment 8872473 [details]
Bug 1107364 - remove findNodeByDetails and maintain a map to fetch a node by details speedily,

https://reviewboard.mozilla.org/r/144002/#review156786

Awesome, r=me with a green-ish Try Run. You can likely limit it to mochitests.
Also please rebase on top of a current mozilla-central so it will be easier to autoland.
Then please needinfo-me for landing (I honestly don't recall if it's enough to have a review to autoland or not, regardless I can do that).

Comment 35

[Milind L (:milindl)]

Comment on attachment 8872473 [details]
Bug 1107364 - remove findNodeByDetails and maintain a map to fetch a node by details speedily,

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/144002/diff/3-4/

Comment 36

[Milind L (:milindl)]

Here goes the try run: https://treeherder.mozilla.org/#/jobs?repo=try&revision=ca5f51a5d96adbfdde94557b0c89dc812caca587
Please see if there are any issues with it.

PS: I fixed my mozreview thing so I can trigger a try build from there next time onwards; but I'd already triggered this one by that time.

I've also rebased off m-c in the latest commit, so landing should be possible.

Comment 37

[Marco Bonardo [:mak]]

Thank you, triggered autoland.

Comment 38

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/87b2b354ed01
remove findNodeByDetails and maintain a map to fetch a node by details speedily, r=mak

Comment 39

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/87b2b354ed01