Async branch

[agzam]

I thought instead of piling every tiny notion about async-branch-related things in the issue #17, maybe better to have a thread here?

[agzam]

@armindarvish, perhaps sorting consult-web-multi results isn't the best? Maybe records should appear according the consult-web-dynamic-sources?

[agzam]

Hmm.. setting :sort to nil doesn't do anything... This is the consult thing, maybe we should ask @minad

[minad]

Not sure if I can help. :sort=nil only sets the display-sort-function and cycle-sort-function to identity to prevent the completion UI from reordering the completion candidates.

[agzam]

Hmmm, so how does consult sort the groups? Unrelated to consult-web, if I for example would want to Files appear before Buffers in consult-buffer, can I do that? Or that's totally unrelated, because consult-multi works differently? Sorry, if I'm throwing totally nub questions. I'm just trying to figure out if it's something on my machine, or consult-web does need to do something else to get the sources appear according to the list.

[armindarvish]

@agzam Let me play around a bit and see if I can reproduce what you are describing with random orders.

But, at least so far my experience is that the :sort t can push the last selected candidate to the top of the list (although there are some gotchas there because it depends on the history variables), which I think is a useful feature (and my intended behavior). Other than that the order of sources should be the same as the order in consult-web-dynamic-sources. But keep in mind that not all of them arrive at the same time in an async process, so sometimes they arrive later but they should get pushed in the right place.

[armindarvish]

Hmmm, so how does consult sort the groups? Unrelated to consult-web, if I for example would want to Files appear before Buffers in consult-buffer, can I do that? Or that's totally unrelated, because consult-multi works differently? Sorry, if I'm throwing totally nub questions. I'm just trying to figure out if it's something on my machine, or consult-web does need to do something else to get the sources appear according to the list.

@agzam, consult-buffer sorts the group based on the order in the list consult-buffer-sources, that is at least the case in my setup. Note that other packages may reorder the candidates for you as well. But consult-buffer itself creates a list of candidates that is a concatenate of the candidates from each source and passes this list to completing-read.

[agzam]

requiring consult-web-sources.el breaks it for me, since I don't have for example consult-notes installed (I use org-roam). I have to manually call consult-web-sources-load-modules with a hard-coded list.

[armindarvish]

@agzam so what happens if you do something like this:

(setq consult-web-sources-modules-to-load '(consult-web-google consult-web-wikipedia))
(require 'consult-web-sources)

in that order. do the (require consult-web-sources) after setting consult-web-sources-modules-to-load.

[agzam]

I'm not very fond of this approach, I think in some cases this may fail. Certain package managers like 'straight' (used in Doom) might alter the loading order or handling due to lazy-loading features or deferred initialization. This could potentially cause the package loading before the var initialized and still breaking things.

[armindarvish]

@agzam I see your point, but I'd rather solve them when they happen. We can of course do some (featurep ...) test as you suggested, but that can also cause its own issues with lazy loading as well.

Note that this is only an issue of getting the init order right, so it only happens once at startup and I think it's fair to expect the user to understand how the packages are being loaded and make sure the order is right. Let's think of it like this, if I break apart the code and put each source in consult-web into its own package (which is I think what would happen if we want this in MELPA), then the right thing to do would be to use (require ...) for loading the requirements in each .el file and it's up to the user to make sure the requirements are in place when loading each package (with or without lazy loading). In such case it won't make any sense to do a featurep test for the main requirements of the .el file. I feel like this is the same here. If the user does not have consult-notes loaded, there is no point loading consult-web-notes to begin with and therefore the user has to figure out how to take care of that in their init.

That said, I am open to trying suggestions, I just don't see any specific solution so far that is better than what we are doing now. So if you have any particular suggestion, let me know what and why you think that would be better

[agzam]

therefore the user has to figure out how to take care of that in their init

Perhaps you're right; depending on "inner magic" isn't always the best. I also don't want you to get overwhelmed by the minutiae of such small details. The package is already extremely valuable, nitpicking every tiny aspect would only hinder the progress.

[armindarvish]

@agzam This is not overwhelming at all. It's good to discuss possibilities and see different options and users' points of view. So feel free to bother me with those details. Worse case scenario I just won't have time to respond and will ignore them 😀.

[agzam]

@agzam See if DuckDuckGo is now fixed (in async branch)!

So, the problem with DuckDuckGo is that it appears to only working for single word searches and it doesn't work if you enter multiple, space-separated clauses. Google and Brave in contrast work for both.

Oh wait... no, I'm wrong. It does sometimes work for multi-word searches, hmm, I guess DDG API is just weird.

[armindarvish]

@agzam The DDG API is just a weird mish-mash that returns a list of suggested related topics; so it is basically doing autosuggestions, but at the same time cannot really deal with typos, and is not always consistent in what it returns either. In general, it's not really that useful, therefore to be honest with you I have spend so little time on it, because I don't see the point of this API! I hope that one day DDG starts providing a real API for the search result (rather than links to related topics) but I think their providers (a.k.a. Bing) does not allow that so I have little hope for it!

[armindarvish]

Update:

I looked into ths a bit more closely, and I think I now understand why the order of the groups seem random.

In the original design of consult--multi, a vector of length equal to number of sources is used to push the candidates of each source into its fixed position and then the vector is flattened into one list. That is all good for a synchronous candidate collection like consult--multi becuase at the end we have all the candidates in the vector and can flatten it. However, in consult-web, where we have a mix of sync and async sources, the list of candidates arrive at different times. We can take a similar approach and make a vector and push candidates in a fixed position, however with the current design we need to flatten the vector to a list and pass this list to the async funciton to update candidates. That would mean that we have to keep a copy of the vector and keep it growing so when we flatten the list, the previous candidates and their order are not lost. I tried this approach earlier based on @karthink's prototype, but at some point I hit challenges with keeping up with the growing vector. It was affecting the performance (because I was sending a growing large vector form one function to another). Sometimes the candidates were even getting lost, I am assuming because of time overlap between different sources and how flattening the vector was overriding the other candidates in the list. So then, I decided to stop tracking the position of each source and just push the new candidates to the end of the list as they arrive and rely on vertico grouping to then put them together in a group. This works but seems to have the disadvantage that the order of the groups is going to depend on the arrival time of items and not on the list of sources. I have not been able to find the right solution to this yet, but I feel like this should have a simple solution that I am missing. Maybe @minad can help understand what would be the right approach here.

Overall, this is something that would take time for me to work on because right now I am in the process of cleaning up and moving things around with all the new sources I have added. In ym own workflow I am using vertico's cycling (e.g. vertico-next-group and vertco-previous-group) to get to the group I am interested in so the arbitrary order of the groups is not as big of an issue. I think that's a reasonable compromise, until I figure out how to improve the overall sorting of the candidates and the groups.

[agzam]

I am using vertico's cycling

I'm doing the same, and since I have a relatively small number of sources, it doesn't seem like a big deal. I do expect however, for the number of groups to gradually grow, and at some point, it may become impractical to use consult-web-multi as a one-stop shop for all the searches. One would then have to use separate commands, which is less ideal. I, of course, did not initially realize how difficult it would be to get this thing right. Please consider shelving this for now; perhaps a good solution will present itself later.

[armindarvish]

it may become impractical to use consult-web-multi as a one-stop shop for all the searches

That's what I thought too, but to be honest so far I have experimented with quite a bunch of sources and I'm always surprised at how well it works. Usually when things fail, it's because the APIs or some local server/file/elisp/... are failing. In other words, the impracticality does not really come from consult/vertico and retrieving/sorting items but more often from the backend part (e.g. rate-limits on APIs, failure of email servers, slow retrieval from web, etc.)

The other limit is, at some point having one command interface is not going to be complex enough to achieve the kind of searches one wants to do with a specific. For example, I have packed a bunch of functionalities in consult-gh that won't make sense to have in consult-web-gh. So at some point the user has to decide whether to go with the one-shop search or the specific search. That said I think if I add a consult-web-become (like the embark-become) that can jump from the general search to specific search tools, then the one-shop would always be the right choice as the starting point. This of course would take some time to experiment with and develop but I think at the end we can get something much more flexible and powerful than other omni-search tools like spotlight and alfred. In fact, I can already see some advantages over those tools in my own workflow.

[armindarvish]

@minad General question for you. If I have multiple sources (async and sync, ...) and the candidates arrive at random times. Is there a way to force vertico to group them in a particular order (maning defining the order of groups)?

For example, see the screenshot below. I have turned off grouping in this case and as you can see the list of candidates is a mix of items from different sources in the order they arrived.

Right now , when I group them, it seems like vertico is going over the list in a loop and sorts them in groups, and therefore the final order depends on the order in this list (picture below).

For example if the second itme in the first picture from Github (kserge/...) had arrived a little bit later after the items from the notes, then the notes group would end up above Github groups in the second picture. I would like to know if there is an easy way to customize that (or perhaps add an step in the consult-completion-refresh-hooks) to rearrange the groups into a fixed order? How would I go about this?

[minad]

General question for you. If I have multiple sources (async and sync, ...) and the candidates arrive at random times. Is there a way to force vertico to group them in a particular order (maning defining the order of groups)?

I am not sure how much my answer applies to asynchronous sources. In Consult, the order of sources is as given. If we don't look at Consult and only at Vertico, the order of the candidates is all that counts when controlling the order of the groups. The group of the first candidate comes first and so on. So what you can do is to create a list of buckets for all the candidates and then join the lists in the desired order. This is how Consult sources operate.

[armindarvish]

I am not sure how much my answer applies to asynchronous sources. In Consult, the order of sources is as given. If we don't look at Consult and only at Vertico, the order of the candidates is all that counts when controlling the order of the groups. The group of the first candidate comes first and so on. So what you can do is to create a list of buckets for all the candidates and then join the lists in the desired order. This is how Consult sources operate.

Yes I understand all that, but I am not sure how to implement an efficient solution here. On the consult side, I think building a list of candidates as they come in (a.k.a. adding async candidates that arrive to the end of the list as they arrive) is much more performant than having to keep buckets and adding them in the right place. In addition the async sink takes a flat list and not "list of lists" or "vector of lists", so having the buckets is not so clean to handle with this back-and-forth between list of lists and flat lists as new async candidates have to be appended to the right bucket. So I am thinking it would be better to do a reorder either on the vertico side or right before vertico, for example by adding a reorder function in the consult-refresh-hooks. But I am not sure if my thought process is right here and was wondering if you have ideas/suggestions on that?

[minad]

Well, I think the most efficient way to solve this is to keep references to the end cons cell of each source. Then you can mutably insert at point. Right now the consult--async-sink also appends mutably in that way, in constant time.

[minad]

In any case I really hope that we can add such facilities to Consult itself, such that all these asynchronous source details are abstracted away.

[armindarvish]

Well, I think the most efficient way to solve this is to keep references to the end cons cell of each source. Then you can mutably insert at point. Right now the consult--async-sink also appends mutably in that way, in constant time.

Hmmm, that sounds like a great idea but I'm afraid it might be beyond my comfort zone to implement right now, so I guess all I have to do is wait for you to get it in Consult! 😃

[karthink]

Well, I think the most efficient way to solve this is to keep references to the end cons cell of each source. Then you can mutably insert at point. Right now the consult--async-sink also appends mutably in that way, in constant time. Hmmm, that sounds like a great idea but I'm afraid it might be beyond my comfort zone to implement right now, so I guess all I have to do is wait for you to get it in Consult!

That seems pretty straightforward, I can take a crack at it sometime.

…

— Reply to this email directly, view it on GitHub <#29 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACBVOLC75FQIBLFF4KYCZB3ZIRWLPAVCNFSM6AAAAABJQ47IYWVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM4TQNBSHAZTM> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[armindarvish]

@minad and @karthink Thinking about this inserting at point, I am now curios, form a low-level memory perspective, how does a list of lists, with growing sub-lists get stored? I am not a computer scientists and don't understand the low-level memory handling at all, but intuitively I think inserting items in the middle of a list (even if we keep reference to the cons cell and insert at point) would require moving things around in the memory and can become expensive once you have thousands of items in the list. But I have no idea how emacs handles any of this, so I am curious to learn if any of you can shed some light on that.

[karthink]

I'll take a look at implementing minad's suggestion soon.

[karthink]

Emacs lists are singly linked cons cells, so inserting in the middle is free if you have a reference to the address of that cell. It just needs to change a few pointers, no data needs to be moved in memory. (Conversely, non-sequential access is expensive since you have to move through the list cell by cell to find the nth element.) I'm not a programmer either, so minad can correct me if I'm wrong.

…

On Fri, Jun 21, 2024, 12:22 PM Armin Darvish ***@***.***> wrote: @minad <https://github.com/minad> and @karthink <https://github.com/karthink> Thinking about this inserting at point, I am now curios, form a low-level memory perspective, how does a list of lists, with growing sub-lists get stored? I am not a computer scientists and don't understand the low-level memory handling at all, but intuitively I think inserting items in the middle of a list (even if we keep reference to the cons cell and insert at point) would require moving things around in the memory and can become expensive once you have thousands of items in the list. But I have no idea how emacs handles any of this, so I am curious to learn if any of you can shed some light on that. — Reply to this email directly, view it on GitHub <#29 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACBVOLB344VKRJXRTZQKUSLZIR4OTAVCNFSM6AAAAABJQ47IYWVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM4TQNBTGEZTO> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[agzam]

afaik, Elisp lists are not the most efficient for inserting in the middle, they have O(n) complexity. A bit more efficient for inserting in the middle is a vector, but they too, have O(n) time complexity. The most efficient thing for middle insertions and deletions in Elisp is I think a "gap buffer", but they are not suitable for this stuff - keeping URLs and their descriptions.

[minad]

Ag Ibragimov ***@***.***> writes:

afaik, Elisp lists are not the most efficient for inserting in the middle, they have O(n) complexity. A bit more efficient for inserting in the middle is a vector, but they too, have O(n) time complexity. The most efficient thing for middle insertions in Elisp is I think a "gap buffer".

No, this is not correct as long as you keep a reference to the insertion point. This is what I'd propose. Then complexity is O(1).

[karthink]

afaik, Elisp lists are not the most efficient for inserting in the middle, they have O(n) complexity. A bit more efficient for inserting in the middle is a vector, but they too, have O(n) time complexity. The most efficient thing for middle insertions in Elisp is I think a "gap buffer".

In the current context, we have a reference to the insertion point in the list so it's very cheap, no traversal necessary. —

…

Reply to this email directly, view it on GitHub <#29 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACBVOLEKODN7PA7BUTLCIYTZIR5ZRAVCNFSM6AAAAABJQ47IYWVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM4TQNBTGIYTA> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[karthink]

@armindarvish How is the async branch doing apart from the Consult core? I have some ideas to make the gptel source more useful, and to make the Elfeed source faster/use less memory. If you're interested and the basic structure of the source definitions etc is finalized, I can work on PRs now -- or wait until the async branch is done.

[armindarvish]

@karthink, it's going pretty well. Right now I am in the process of moving the async branch to a new repository (consult-omni), which solves some of the current issues and also adds a bunch of new useful sources. I am doing some clean up before I announce it in the coming weeks.

Suggestions are always appreciated but I'd think it would be better if you wait for the new repo and we can improve gptel and elfeed there.

If you have time I think it would be great if you can start prototyping with minad's idea for inserting candidates in the source list where they belong. I have an explanation here that gives you an idea exactly where the problem is.

Other relevant background for you:

If you have not looked at the code for a while, note that there is a new universal collector consult-web--multi-update-candidates that essentially combines consult--async-process and consult--dynamic-compute. So I ended up going by having the user declare the type of source ('sync, 'dynamic, or 'async) and use that to call the right collector function as opposed to guessing it by number of input arguments or catching errors. Compared to what you had in your prototype, this has the disadvantage that it does not work with current consult sources as is, so I had to redefine and make a consult-web counterpart to other sources (like consult-grep, consult-buffer, ...) but I think this is the right way of doing it (at least in consult-web) as opposed to trying to keep this backward compatible for current consult sources.

In the process of building the new universal collector, I ended up getting rid of making a vector placeholder for each source list (e.g. '[(list) (list) (list)]) and therefore the approach with pushing the the candidates to this vector and then flattening it for consult--read is not there anymore. Ideally we would want a well-performing sorting (like minad's suggestion) to be implemented with the new universal collector, and my feeling is that we may end up reimplementing consult--async-sink but since I have already replaced several pieces of consult with their consult-web's counterpart, I think it would be OK if we end up doing that, too.

[armindarvish]

alright consult-omni is now public. We can move the rest of this discussion there. I made one topic already for sorting the groups: armindarvish/consult-omni#1