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

RESOLVED FIXED in Firefox 56

Status

()

defect
P2
normal
RESOLVED FIXED
5 years ago
2 years ago

People

(Reporter: mano, Assigned: milindl, Mentored)

Tracking

(Blocks 1 bug, {perf})

unspecified
Firefox 56
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox56 fixed)

Details

(Whiteboard: [lang=js][fxsearch][qf:investigate:p1])

User Story

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.

Attachments

(1 attachment)

yep, the current situation doesn't make any sense...
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).
Priority: -- → P2
Blocks: 734643
Comment hidden (obsolete)

Comment 4

3 years ago
I'm planning to submit a patch for this bug as part of an assignment for CSC302 at the University of Toronto.
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

3 years ago
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!
Blocks: 1268855
Summary: inline findNodeByDetails in treeView.js and remove it from nsINavHistoryResultNode → move findNodeByDetails to treeView.js and make it use an hash
User Story: (updated)

Comment 7

3 years ago
Hi Jonathan,

Are you still working on this bug? If you are not I would like to work on this.
Flags: needinfo?(mak77)

Comment 8

3 years ago
Hi Amila,

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

Comment 9

3 years ago
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?
(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?
Flags: needinfo?(mak77)
Whiteboard: [good first bug][lang=js] → [good first bug][lang=js][fxsearch]

Comment 11

3 years ago
Hi, I would like to work on this bug. Is that possible?
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.
while this is mentored, it's not a [good first bug]
Whiteboard: [good first bug][lang=js][fxsearch] → [lang=js][fxsearch]

Comment 14

3 years ago
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!
Flags: needinfo?(mak77)
I'm not sure I got the question, but yes, this code is used by history treeviews in Firefox.
Flags: needinfo?(mak77)

Comment 16

3 years ago
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.
Flags: needinfo?(mak77)
(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"
Flags: needinfo?(mak77)

Comment 18

3 years ago
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.
Flags: needinfo?(mak77)
(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).
Flags: needinfo?(mak77)
Whiteboard: [lang=js][fxsearch] → [lang=js][fxsearch][qf]

Updated

2 years ago
Whiteboard: [lang=js][fxsearch][qf] → [lang=js][fxsearch][qf:investigate:p1]

Comment 20

2 years ago
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.
(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 hidden (mozreview-request)
Assignee

Comment 23

2 years ago
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!
(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.
Assignee

Updated

2 years ago
Depends on: 1368754
Assignee: nobody → i.milind.luthra
Status: NEW → ASSIGNED
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.
Attachment #8872473 - Flags: review?(mak77)
Assignee

Comment 26

2 years ago
> 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.
Assignee

Comment 27

2 years ago
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.
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 hidden (mozreview-request)
Assignee

Comment 30

2 years ago
> 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

2 years ago
mozreview-review
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.
Attachment #8872473 - Flags: review?(mak77)
Assignee

Comment 32

2 years ago
mozreview-review-reply
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 hidden (mozreview-request)

Comment 34

2 years ago
mozreview-review
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).
Attachment #8872473 - Flags: review?(mak77) → review+
Comment hidden (mozreview-request)
Assignee

Comment 36

2 years ago
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.
Flags: needinfo?(mak77)
Thank you, triggered autoland.
Flags: needinfo?(mak77)

Comment 38

2 years ago
Pushed by mak77@bonardo.net:
https://hg.mozilla.org/integration/autoland/rev/87b2b354ed01
remove findNodeByDetails and maintain a map to fetch a node by details speedily, r=mak
Keywords: perf

Comment 39

2 years ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/87b2b354ed01
Status: ASSIGNED → RESOLVED
Closed: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → Firefox 56
You need to log in before you can comment on or make changes to this bug.