# Suggestion: concurrent\_findall **URL:** \ **Category:** Request For Comments\ **Created:** [July 12, 2020, 6:45pm UTC](https://swi-prolog.discourse.group/t/suggestion-concurrent-findall/2628 "2020-07-12T18:45:29Z")\ **Posts on this page:** 12\ **Page:** 1
**Author:** ![swi](https://avatars.discourse-cdn.com/v4/letter/s/51bf81/32.png) [@swi](https://swi-prolog.discourse.group/u/swi)\ **Post date:** [July 12, 2020, 6:45pm UTC](https://swi-prolog.discourse.group/t/suggestion-concurrent-findall/2628/1 "2020-07-12T18:45:29Z")
I was thinking (for a use case I have now) it would be a good idea to have a: ```prolog concurrent_findall(+Template,:Goal,-Bag,:Sort,Opts) ``` This predicate would work like findall/3 but would do the following: 1. Start several threads and run `Goal` in each thread, to partially fill the `UnsortedBag` 2. Use Opts for thread creation or other options 3. Run `Bag=Sort(UnsortedBag)` to sort the results in the user-expected order This is very useful for when you have a large database and you want to search it, but need to keep the search order in the results. This assumes the search result is much smaller (in size) than the database, which is usually the case. What do you guys think? EDIT: Goal would be called as `call(Goal,ThreadNumber)` so that the user can decide how to partition the search inside the goal. ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [July 12, 2020, 6:59pm UTC](https://swi-prolog.discourse.group/t/suggestion-concurrent-findall/2628/2 "2020-07-12T18:59:24Z")
> [@swi](#): > > a large database and you want to search it, but need to keep the search order in the results. In the database world, it’s considered a bad idea to depend on search order of results (IIRC, the SQL spec says that you can’t depend on it unless you have an ORDER BY). In they Python world, it’s a bad idea to depend on the ordering of items stored in a hash table (“dict” - see PYTHONHASHSEED). Etc. ---
**Author:** ![swi](https://avatars.discourse-cdn.com/v4/letter/s/51bf81/32.png) [@swi](https://swi-prolog.discourse.group/u/swi)\ **Post date:** [July 13, 2020, 1:11am UTC](https://swi-prolog.discourse.group/t/suggestion-concurrent-findall/2628/4 "2020-07-13T01:11:17Z")
> [@peter.ludemann](#): > > In the database world, it’s considered a bad idea to depend on search order of results I meant the application/business logic needs the results in a certain order; just like it is guaranteed by findall/3 in a single-threaded app. Because findall/3 would already returns the results in the proper order, it would be fitting for concurrent\_findall/3 to do the same also or at least to allow it. This is the purpose of the :Sort goal, which would be set to return its input if one doesn’t care about sorting the results. ---
**Author:** ![swi](https://avatars.discourse-cdn.com/v4/letter/s/51bf81/32.png) [@swi](https://swi-prolog.discourse.group/u/swi)\ **Post date:** [July 13, 2020, 1:34am UTC](https://swi-prolog.discourse.group/t/suggestion-concurrent-findall/2628/5 "2020-07-13T01:34:31Z")
> [@anon95304481](#): > > ```prolog > concurrent_and_sorted(G, T) :- > term_variables(G+T, X), > bagof(X, concurrent_and(call_nth(G, _), T), L), > member(X, L). > > ``` Interesting trick, I’ll play with it some. I still think that a `concurrent_findall/_` in the api would be useful though. ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [July 13, 2020, 1:51am UTC](https://swi-prolog.discourse.group/t/suggestion-concurrent-findall/2628/6 "2020-07-13T01:51:37Z")
> [@swi](#): > > the application/business logic needs the results in a certain order; just like it is guaranteed by [findall/3](https://www.swi-prolog.org/pldoc/doc_for?object=findall/3) in a single-threaded app In the database world, where performance is gained by sophisticated indexing, parallelism, replication, and sharding, if you want to have results in the same order you put them in, then you should have a field that contains that ordering information (a time stamp, a sequence number, etc.). It’s a bad idea for people to depend on `asserta`/`assertz` and `bagof`/`findall` ordering for their results (and even worse if they depend on the data being in bags with possible duplications). A SQL “ORDER BY” isn’t necessarily a performance problem - there’s often no need to sort the results because there can be indexes that have the ordering information already computed. (One of my pet interview questions for people who claimed database expertise was to ask them why b-tree organization was often preferred over hash indexing, even though hash indexing has _O(1)_ lookup cost vs _O(log N)_ for b-trees.) ---
**Author:** ![swi](https://avatars.discourse-cdn.com/v4/letter/s/51bf81/32.png) [@swi](https://swi-prolog.discourse.group/u/swi)\ **Post date:** [July 13, 2020, 2:22am UTC](https://swi-prolog.discourse.group/t/suggestion-concurrent-findall/2628/7 "2020-07-13T02:22:45Z")
> [@peter.ludemann](#): > > It’s a bad idea for people to depend on `asserta` / `assertz` and `bagof` / `findall` In my use case, the ordering is not dependent on assert, but because the desired order never changes (it is an invariant in this domain), it is simply a set of facts in a source file. Therefore there is no danger here. Nonetheless, I agree with you in the general database case. Nonetheless, both cases can be properly handled by the proposed `concurrent_findall/_`. ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [July 13, 2020, 2:39am UTC](https://swi-prolog.discourse.group/t/suggestion-concurrent-findall/2628/8 "2020-07-13T02:39:00Z")
> [@swi](#): > > the desired order never changes (it is an invariant in this domain), it is simply a set of facts in a source file. That’s the same as using assertz/1. Even if it makes no difference now, I would caution against any guarantees in the order of results from `concurrent_findall`. (The original implementors of SQL took some shortcuts that seemed reasonable at the time but which prevented many useful optimizations later, and which also introduced many subtle inconsistencies in the query language.) ---
**Author:** ![swi](https://avatars.discourse-cdn.com/v4/letter/s/51bf81/32.png) [@swi](https://swi-prolog.discourse.group/u/swi)\ **Post date:** [July 13, 2020, 2:41am UTC](https://swi-prolog.discourse.group/t/suggestion-concurrent-findall/2628/9 "2020-07-13T02:41:21Z")
> [@peter.ludemann](#): > > I would caution against any guarantees in the order of results from `concurrent_findall` The order of results, in my proposal, is guaranteed by calling the user-defined `Sort` goal, not by anything else. ---
**Author:** ![swi](https://avatars.discourse-cdn.com/v4/letter/s/51bf81/32.png) [@swi](https://swi-prolog.discourse.group/u/swi)\ **Post date:** [July 13, 2020, 2:42am UTC](https://swi-prolog.discourse.group/t/suggestion-concurrent-findall/2628/10 "2020-07-13T02:42:12Z")
I tried your porposal with `concurrent_and` and got a 2-2.5 speed up , not bad. ---
**Author:** ![EricGT](https://avatars.discourse-cdn.com/v4/letter/e/f1d935/32.png) [@EricGT](https://swi-prolog.discourse.group/u/EricGT)\ **Post date:** [July 13, 2020, 9:28am UTC](https://swi-prolog.discourse.group/t/suggestion-concurrent-findall/2628/11 "2020-07-13T09:28:25Z")
Perhaps what you seek is a cousin to [library(solution\_sequences)](https://www.swi-prolog.org/pldoc/man?section=solutionsequences) but instead of working with findall/3 , create a new predicate concurrent\_findall/3 (which might be concurrent\_and/2 or concurrent\_maplist/2 ([ref](https://stackoverflow.com/q/49036185/1243762))) and then the cousin library ( library(concurrent\_solution\_sequences) ) would work with concurrent\_findall/3. ---
**Author:** ![PeterChan](https://avatars.discourse-cdn.com/v4/letter/p/7bcc69/32.png) [@PeterChan](https://swi-prolog.discourse.group/u/PeterChan)\ **Post date:** [February 14, 2021, 8:59pm UTC](https://swi-prolog.discourse.group/t/suggestion-concurrent-findall/2628/13 "2021-02-14T20:59:53Z")
Cosytec proposed the partial search strategy to explore huge search spaces. You may be interested in implementing it in SWI in a concurrent fashion. Here is the paper title: N. Beldiceanu, E. Bourreau, P. Chan, and D. Rivreau. Partial search strategy in CHIP. In 2nd International Conference on Metaheuristics - MIC 97, Sophia Antipolis, France, July 1997. ---
**Author:** ![joeblog](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/joeblog/32/122_2.png) [@joeblog](https://swi-prolog.discourse.group/u/joeblog)\ **Post date:** [February 16, 2021, 5:52pm UTC](https://swi-prolog.discourse.group/t/suggestion-concurrent-findall/2628/14 "2021-02-16T17:52:15Z")
The way I do this is to first _listify_ whatever the inputs to :Goal1 in [**findall** (+Template, :Goal1, -Bag1)](https://www.swi-prolog.org/pldoc/doc_for?object=findall/3) are (using findall/3 to get them from the clausal store), then using [**concurrent\_maplist** (:Goal2, +Bag1, -Bag2)](https://www.swi-prolog.org/pldoc/doc_for?object=concurrent_maplist/2). I guess it would be more efficient to figure out how to do this without the initial traversal through the clausal store.