Improve the performance of dimension capturing

[alexreardon]

Currently there is a DIMENSION_COLLECTING phase before a drag where we request the dimensions for all of the Droppable and Draggable components. This is quite expensive as it calls .getBoundingClientRect and window.getComputedStyle on all the nodes. We need to think more about how we could improve the performance of this. Some options off the top of my head:

• (simplier) find a cheaper way of getting the margin values off an element. I had a look and I could not find one, but it is worth further investigation
• (simplier) allow drag movement before all the dimensions are requested (this would not help with keyboard dragging)
• (more complex) only request a batch of dimensions (such as those in the current viewport) and request more dimensions as needed. This is tricky because it may jank the scroll, and also will change how we calculate the index of the current item.

[poryzhao]

@alexreardon
I found the performance Issue you recorded several days ago and I encountered the same performance problem.

The method getDimension in the file draggable-dimension-publisher.jsx will be called xx times if I get xx lanes or xx cards in a board, it costs a long time and a user may give up this drag behavior and tell us the lane or card can't drag anymore.

I found you get several ideas and just want to know when this performance issue will be supported? thank you so much!

[alexreardon]

Yeah, right now we collect everything before we allow any movements (simple approach to start with). We are hoping to make this more async. Right now our focus is on auto scrolling and touch support. Although, I am keen to tackle this once those and some other core features are built. For now we are totally open to suggestions on how to make this phase faster. I suspect we wont be able to make it faster, so we will need to make it more async.

[alexreardon]

It is currently contained in the Fire Kingdom milestone: https://github.com/atlassian/react-beautiful-dnd/milestone/3

[poryzhao]

@alexreardon thank you so much for your information and hope those performance bottle necks can be solved soon!

[alexreardon]

Some thoughts about this one:

When can we capture dimensions?

On mount ?
No. The shape of a component can change based on its props after a mount, and we do not want to publish a new dimension on every update

On mouse down (before drag start)
This would buy us a little time - but not much - especially if the user is moving their mouse quickly. It does also not help with keyboard dragging.

On drag start
Seems like the best place

Moving to async dimension capturing

Right now we request all of the dimensions on drag start (in the DIMENSION_COLLECTING phase). However, we can lift this restriction so that dimensions can be published during a drag. This means the user could start moving the item around before we have captured all of the dimensions. The impact of the users drag would be limited to the dimensions we have collected.

Solutions in order of complexity

1. Publish all dimensions instantly, but do not block user dragging

This is almost the same as it is now, except we allow the user to move the item around before the dimensions are captured.

Issues:
How do we know the initial index of the item? (This is published as part of onDragStart).

Simple answer: no longer publish the original location on drag start. I could be persuaded that this is not critical information
Harder answer: figure out a fast way to know an items index within a list. As long as React calls render (or one of the update hooks) on items in a list sequentially then items could publish themselves and we would know the order simply by knowing the order that things where returned in. However, I am not sure if that always holds true.

Keyboard movement
Unlike mouse movement, we cannot move a keyboard item until the dimensions are collected - at least it's siblings

2. Building on solution 1: collect dimensions in batches

The core idea of this is that we collect the dimensions closest to the lifted Draggable first and work outwards from there - collecting some small number of dimensions at a time (eg 10). If we know the index of each item when the drag starts, then we could implement a batched collection. We could also figure out heuristics for other lists: eg collect dimensions in all droppables within +-5 of the selected index and work outwards in batches of +-5. This would generally yield good results for sibling lists unless the items are drastically different in size.

If we assume that we can generate just the centre position of each item really quickly, then the batches could be based on distance from the draggable rather than index. I would need to investigate, but I strongly suspect that getBoundingClientRect is much cheaper than window.getComputedStyle. In which case, we might be able to call getBoundingClientRect on everything at the start. This information can then be used to measure the distance from the lifted item to calculate the waves.

3. Visible dimensions gathering

Rather than collecting the dimensions for all Draggables, rather we only collect dimensions for ones in the current viewport. As the user scrolls, we would collect the dimensions for draggables that have not been collected yet. Putting anything on scroll is a little dangerous as it is likely to cause jank. However, if it is done well with requestAnimationFrame etc then it might be feasible. This solution would need to consider window scroll as well as container scroll

[Hivemind9000]

Hi Alex. First of all, thank you for such a great utility. I've run into this problem (100+ draggables in 40+ droppables) and the drag-lag has become a bit of a show stopper (500ms+ delay when starting a drag operation). I have checked out your code and approach and have a very cursory understanding of how it all works (I will look into it more).

It seems that, no matter what you do, there will always be a risk of scaling/performance problems if you collect the dimensions while the user is trying to drag something - especially for users on lower spec machines, and for apps where the number of draggables/droppables can vary significantly (as well as screen sizes). Instant feedback on starting a drag operation is critical from a UX perspective.

I have a few thoughts/questions/ideas to start with:

Why can't the dimensions be calculated in the componentDidUpdate phase of draggables/droppables? I assume these would only be called when something actually updated within the draggable/droppable hierarchy, and so should be reasonably spread out over time. Any rendering operation could be flagged so that the dimensions are not recalculated while dragging is active?

I noticed that you store the current window scroll position when calculating the dimension. This would need to be separated out if you were calculating dimensions during the componentDidUpdate phase (and factored back in dynamically when doing drag/bounds calculations - when getting the clientRect perhaps?).

Could there be a way to allow the developer (i.e. me) a way to flag the parent draggable/droppable when something changes (i.e. manual/controlled recalculation of dimensions)? Some sort of redux or HoC thing? A little bit brute force, but could be a potential option if all else fails.

Forgive me if I've got the wrong end of things. Just trying to help seed ideas or options. It would be good to understand the problems around the above approach, which may help me look at it again with new eyes.

[ibarkowski]

Hi Alex, thanks for a great tool. Good work. I wonder if you have any other thoughts about this issue. My team would like to use this utility in our new application, and we have the same performance problems with drag and drop components. Do you have any idea how to fix that?

[alexreardon]

I hope to work on this after Candy castle milestone lands

[alexreardon]

I have been thinking about this one while away and I have ideas to try out!

[alexreardon]

Building on my previous comment I thought of a way to get the index's before the dimensions.

Right now we have a COLLECTING_DIMENSIONS phase were we collect all the dimensions. Here is some more thoughts:

1. Have a COLLECTING_INDEXES phase in which all the components simply respond to a request to publish. The order in which these responses are received will be the order of the components based on how react works today. This phase may also be extended to include whether the component is currently visible (assuming this is super cheap to calc)
2. Once we have the indexes we can start the drag and async collect the dimensions

This would allow the drag to start almost instantly while allowing future batching of dimension collecting using a number of different possible techniques

[poryzhao]

Do you have any progress on this issue? still waiting to use react-beautiful-dnd after this issue is settled. @alexreardon

[alexreardon]

I had a great idea on how to do this. I will share the details next week

[alexreardon]

Okay, so here is my current plan:

(details still super fuzzy)

The dimension marshal

Right now we need to request all the dimensions of everything before we start. The key idea is to make this more async. This will also facilitate virtualisation techniques. I propose introducing a new powerful actor: the dimension marshal. This actor would be a lot smarter than what we have today and would allow more creative capturing techniques

Phase 1: registration on mount

When a Draggable or Droppable mounts they register themselves with the marshal. Ideally at this phase we would know their position in the list to avoid needing to find this out later. This is complicated because components might be removed or added before the drag starts.

Phase 2: initial lift

In order to lift we only need to capture a subset of the total dimensions:

• the dimension of the current Draggable
• the dimension of the home Droppable
• (possibly the dimensions of all the Droppables to make things really simple)

At this point we should have enough information to start a drag

Phase 3: phased collection

In this phase the marshal will request dimensions in batches in increasing distance from the source draggable. Both within the current list as well as other lists. We get a number of advantages in this:

• we do not need to wait for all the dimensions before we start dragging
• the things closest to the draggable are most likely to move first so we optimise their collection
• we can batch updates to the store so that we do not trigger as many memoization checks (we can publish a list of dimensions in an action rather than just one at a time)

This phase is still to be figured out completely. There may be some sort of visibility check added - although these are often expensive so we might as well just collect the dimension.

Phase 4: Draggables mounted mid drag

This is what would occur in a virtualised list - draggables would be mounted within a drag. We would need to cater for draggables mounted within a Drag to be added to the dimension pool and interacted with. Depending on how the virtualised lists work we may also need to account for Draggables unmounted mid drag.

Some thoughts 🤔

• Right now we use a react render to figure out the order of things. If we can avoid this then we can get around a lot of redundant checks. The marshal might be able to communicate directly with components without needing a render cycle if we can get the order somehow. We might still need to do this to get the order pre-drag - but we should use shouldComponentUpdate to block a child render in this case

[alexreardon]

More thoughts: required index prop

I have been wrestling with how to dynamically get the index of a Draggable. It is possible to do, but it involves touching every Draggable which is not ideal. Also it gets really confusing when it comes to virtual lists with mounting and unmounting happening a lot to maintain correct indexes. I am thinking the fastest and safest course of action is to add an index prop to Draggable.

Advantages:

• Can register a Draggable on mount with its correct index. The list can be easily maintained by using standard lifecycle methods.
• Virtual lists become a lot simplier as we know the index in the list on mount rather than needing to measure anything

I do not think this is too much of a burden given that consumers will probably be generating a list of Draggables in a loop anyway.

[Hivemind9000]

I wasn't sure if you were looking for feedback, but here's mine anyway... :)

My only concern is capturing all Droppables' dimensions on the initial lift. I can have (easily) 50+ Droppables - almost as many as Draggables - so this would most likely cause a noticeable "hitch" when starting to drag.

I agree - most use cases would be using an internal index of their own to sort their Draggables, so I don't think requiring it as a prop would be much of a burden - especially if it helps with your performance strategy.

Looking forward to it!

[alexreardon]

Good call out regarding the droppable's. We would probably make them phased also. It is a bit tougher because we might also need an index on those which might not make much sense depending on your droppable configuration

[bradleyayers]

I think this is the same problem that react-virtualized solves, so I might try do a bit of study on that library before I contribute to this discussion.

[alexreardon]

Cheers. I think the containers are established up front.

Regarding phased droppables - we can probably do some basic phasing without accurate indexes

[alexreardon]

I think we are getting close to a solution that will scale well regardless of the amount of droppables that you have 💃

To assist with this Droppables may also need to publish some sort of index / order value

[alexreardon]

Early prototype: a 500 card list running at ~60fps with instant lift without virtualisation

[dcporter44]

I'm not sure if I'm having the same issue, but it sounds like it. If I have a large amount of cards, I receive a larger delay. I have about 150 cards, and it takes about a full second from "mouse-downing" to card, to actually picking up the card. The fewer cards I have on the board, the less this delay is. Less than 50, there is little to no delay. Which is confusing because I'm doing absolutely nothing on dragStart. I've put console logs in the render of my columns, and they are definitely not re-rendering on drag start.

[alexreardon]

@dcporter44 that is caused by this issue. It is being actively worked on 👍

[dcporter44]

@alexreardon awesome that prototype looks great.

[alexreardon]

Still a super work in progress (reordering doesn't work, placeholders are busted - it is unstable 💥) but you can have a play with the prototype containing 500 cards

[alexreardon]

Keep in mind that this is 500 Draggable's without virtualisation. Before you would have had a really bad time

[dcporter44]

Speed-wise looks great. Sorry to ask every developer's least favorite question, but how long do you estimate until this is stable? Just trying to time-map out my own project, and trying to decide whether to go figure out React DnD in the meantime

[alexreardon]

@dcporter44 it is currently being actively worked on. I try not to give out dates. I think within the next month as a ballpark is a rough guide

[alexreardon]

Work in progress stats:

Here are some current stats based on the work we are doing. All of the values here are based on a list with 500 Draggables without any virtualisation

Values were recorded on a powerful machine with instrumentation enabled. It would be best to look at the relative differences between the values rather than the values themselves.

Time to lift

master: 2400ms
new: 12ms

200x faster 🤘

Time for movement

the amount of time it takes to render a small movement (keep in mind that 16ms is one frame)

master: 12ms
new: 5ms

2.4x faster 👍

Time for drop

pending

Have a play

super broken prototype to give a rough idea

[Hivemind9000]

Impressive. Do you think multiple droppables will make any (negative) difference to the performance?

[alexreardon]

Nope

[alexreardon]

Updates

• Droppable will not need to provide an index. It is not needed to improve performance
• Additional prop added to Droppable: displacementLimit which allows for a maximum amount of items to be displaced visually during a drag which defaults to 20. The prevents redundant work from being done off screen. And provides a great experience when dragging through huge lists. Consumers can opt out of limiting the amount of displaced items by simply setting the value extremely high, eg 'Infinity'. This is to tackle the problem of moving into a list when it causes a large number of Draggables to be displaced all at the same time

[kenchambers]

great idea with displacementList !
will be monitoring this issue closely , thanks for the update !

@dcporter44

[alexreardon]

I am now looking at removing displacementLimit and using a visibility check to control item displacement 👍

It is tricky to get working, but my initial results are really promising

[alexreardon]

The results for this piece of work are looking so good that it will drastically reduce the need for #68 as a go to.

[tjramage]

Nice work @alexreardon — the prototype is looking great! We're also experiencing major initial drag lag with boards that have 100's of cards. Just wondering how progress is going on this?

[alexreardon]

Thanks @tjramage. Pull request is getting close #226

[tjramage]

Ah, I didn't see that PR... Awesome. Thanks @alexreardon.

[jethrolarson]

Just saw that checklist is all checked in #226. Getting excited. Is there gonna be an npm publish this week?

[alexreardon]

Yep

…

On Wed, 10 Jan 2018 at 12:38 pm, Jethro Larson ***@***.***> wrote: Just saw that checklist is all checked in #226 <#226>. Getting excited. Is there gonna be an npm publish this week? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#86 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ACFN7TFDe-7bubG4k5YSlgr03pMyHFhzks5tJBR5gaJpZM4PSn8n> .

[alexreardon]

Action	Time before changes	Time after changes	Reduction
Lifting a Draggable	2600ms	15ms	99%
Dragging with small amount of displacement	9ms	6ms	33%
Dragging with large amount of displacement	9ms	6ms	33%
Moving into a large list with small amount of displacement	380ms	4ms	99%
Moving into a large list with large amount of displacement	380ms	8ms	98%
Time to start animation after a drop	370ms	4ms	99%

[bradleyayers]

Well done @alexreardon, thanks for seeing this through! We'll be upgrading Dovetail to use the latest version soon.

[tjramage]

Amazing! Thanks @alexreardon, excited to try this.