Skip to content
New issue

Have a question about this project? # for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “#”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? # to your account

WIP: Trying to fix #5176 #5272

Draft
wants to merge 22 commits into
base: master
Choose a base branch
from

Conversation

AnouarTouati
Copy link
Contributor

@AnouarTouati AnouarTouati commented Jan 6, 2025

This draft is WIP attempt to fix #5176 @jerch

  • Search is done in chunks , in alternating manner up/down so the region the user sees first will be done first.
  • Decorators/markers 's disposal is also done in chunks in the background(a new search can start without waiting for this to finish).
  • Added debounce to the search function.
  • Search is now cancel-able

This is obviously a breaking change.
I tried to go with the conservative approach to keep the code changes to a minimum. But, I had to re-write most of the code.

If this is the direction you want the code to go in. I can keep working on this and maintaining the search addon from now on.
Also ignore the commits I was experimenting with stuff. Will squash them later.

2025-01-06.02-40-30.mp4

@Tyriar
Copy link
Member

Tyriar commented Jan 6, 2025

Adding responses to #5176 (comment) here.

Why does the cache have TTL ?

This is to aid in incremental searches

I experimented with making the search return a small set. release the main thread to render the result and then go and get the full result. i did this with a setTimeout. It helped a lot with the UX.

Something we want to keep is the highlighting of results in the "overview ruler":

Image

Limiting these results too heavily will hurt the UX by not showing additional results. Make sure you add the overview ruler in the demo when working on this:

Image

I noticed that "incremental" search only serves to do the following :
Suppose you have A B D C D in the terminal
Search for C to select it
Then search for D and it selects the second D.
Is this intentional ?

If I'm understanding you correctly, searching for CD second should only check if there is a D after the already existing C:

image

This is by design, incremental search means we can avoid doing much of the work, provided regex is not enabled which I think disables incremental completely.

Maybe another solution is to count the matches but only apply the decorators to the visible lines and a few hidden ones on top and bottom ?

The overview ruler is again an important piece here, see this result which is after running tree on Windows:

image

There are 19 results, and every one of these is represented in the overview ruler, allowing the user to know immediately how far back the term(s) are.

Copy link
Member

@Tyriar Tyriar left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks promising! 👏

Comment on lines 75 to 95
/**
* Number of matches in each chunk
*/
private _chunkSize: number = 200;
/**
* Time in ms
* 1 ms seems to work fine as we just need to let other parts of the code to take over
* and return here when their work is done
*/
private _timeBetweenChunkOperations = 1;

/**
* This should be high enough so not to trigger a lot of searches
* and subsequently a lot of canceled searches which clean up their own
* decorations and cause flickers
*/
private _debounceTimeWindow = 300;
/**
* Using this mainly for resizing event
*/
private _longerDebounceTimeWindow = 1000;
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

There's actually a perfect helper for just this scenario in the main code:

https://github.com/Tyriar/xterm.js/blob/18c9eb196010ec082ad56adf7040ed2dca5fd391/src/common/TaskQueue.ts#L104-L109

This will let you continue to search until the deadline is reached, essentially scaling the solution to high end CPUs that can handle searching a lot more immediately instead of the arbitrary 200 line chunk limit. This is how we draw ascii glyphs to "warm up" the texture atlas without doing any of this optional work in a blocking manner.

https://github.com/Tyriar/xterm.js/blob/18c9eb196010ec082ad56adf7040ed2dca5fd391/src/browser/renderer/shared/TextureAtlas.ts#L118-L129

For your scenario it's important work that the user is waiting on, not optional, so PriorityTaskQueue is more appropriate. It works much the same, just it's backed by setTimeout, not requestIdleCallback.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Here is what I understood and correct me if I am wrong.
I will be en-queuing call back functions (Tasks) that process X number of lines. The task queue will run as many tasks as possible until we exceed the time limit at which point it yields, then do a new setTimeout to start processing of next batch of Tasks.

https://github.com/Tyriar/xterm.js/blob/18c9eb196010ec082ad56adf7040ed2dca5fd391/src/common/TaskQueue.ts#L104-L109

About the race condition comment. I think it arises from line 71 this._idleCallback = undefined; which in my opinion should be removed and inserted above line 95 this.start() that way new enqueue calls wont trigger new setTimeouts.

addons/addon-search/src/SearchAddon.ts Outdated Show resolved Hide resolved
@AnouarTouati
Copy link
Contributor Author

Something we want to keep is the highlighting of results in the "overview ruler":
Limiting these results too heavily will hurt the UX by not showing additional results. Make sure you add the overview ruler in the demo when working on this

I am currently highlighting all of the matches so this will not be a problem.
In the future I will highlight only the the matches that are in the viewport. and highlight everything on the overview ruler.

@AnouarTouati
Copy link
Contributor Author

If I'm understanding you correctly, searching for CD second should only check if there is a D after the already existing C
This is by design, incremental search means we can avoid doing much of the work, provided regex is not enabled which I think disables incremental completely.

No, this is what the incremental flag is doing
Screenshot from 2025-01-06 14-05-20
then replace D with B in the search bar (dont backspace. Do Ctrl + A and overwrite)

Screenshot from 2025-01-06 14-05-59

Notice that the second B is selected.
matches before D are not considered for the first select.

That's all it does. It does not help performance.

I removed this behavior.
I will implement an actual incremental search in the future.

@AnouarTouati AnouarTouati force-pushed the search-start-at-middle-of-view branch from c71ef1b to 6ecf521 Compare January 6, 2025 20:02
@Tyriar
Copy link
Member

Tyriar commented Jan 6, 2025

Notice that the second B is selected.
matches before D are not considered for the first select.

I'd have to play around with it, we just want to make sure it's consistent

# for free to join this conversation on GitHub. Already have an account? # to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Search is too slow
2 participants