Memoize

On Mon, Mar 23, 2020 at 11:05 AM Mickael Desfrenes <mickael.desfrenes at unicaen.fr> wrote: > > Hello dear basex list, > > Is there any known solution for function memoization in basex ? Or maybe a cache implementation ? > > M. Desfrênes > >

On Mon, 2020-03-30 at 15:39 +0200, Christian Grün wrote: > I remember that some users have successfully utilized Memcached in > the past to cache BaseX query results.

On Mon, Mar 23, 2020 at 11:05 AM Mickael Desfrenes < mickael.desfrenes at unicaen.fr> wrote: > Is there any known solution for function memoization in basex ? Or maybe a > cache implementation ? >

De: "Andreas Mixich" <mixich.andreas at gmail.com> Cc: "basex-talk" <basex-talk at mailman.uni-konstanz.de> Envoyé: Samedi 4 Avril 2020 02:55:45 Objet: Re: [basex-talk] Memoize Not sure, whether this went through to the mailing list or only to Mickael, so please, forgive me, if posting twice. On Mon, Mar 23, 2020 at 11:05 AM Mickael Desfrenes < [ mailto:mickael.desfrenes at unicaen.fr | mickael.desfrenes at unicaen.fr ] > wrote: Is there any known solution for function memoization in basex ? Or maybe a cache implementation ? Not sure how much this helps, but there was a Balisage talk by James Fuller, titled [ https://www.balisage.net/Proceedings/vol17/author-pkg/Fuller01/BalisageVol17-Fuller01.html | "A catalog of Functional Programming idioms in XQuery 3.1" ] , which produces (amongst others) a memoize function. It is written in the Marklogic dialect of XQuery. but porting it was a no-brainer, since, AFAIR, only the syntax for maps had to be changed. The [ https://github.com/xquery/xquery_functional_catalog/ | Github repo is here ] . -- Minden jót, all the best, Alles Gute, Andreas Mixich

On Sun, Apr 5, 2020 at 10:34 AM Mickael Desfrenes < mickael.desfrenes at unicaen.fr> wrote: > That's great, just what I was looking for. And the rest of the > presentation is interesting too. > > Thank you ! > > ------------------------------ > *De: *"Andreas Mixich" <mixich.andreas at gmail.com> > *Cc: *"basex-talk" <basex-talk at mailman.uni-konstanz.de> > *Envoyé: *Samedi 4 Avril 2020 02:55:45 > *Objet: *Re: [basex-talk] Memoize > > Not sure, whether this went through to the mailing list or only to > Mickael, so please, forgive me, if posting twice. > On Mon, Mar 23, 2020 at 11:05 AM Mickael Desfrenes < > mickael.desfrenes at unicaen.fr> wrote: > >> Is there any known solution for function memoization in basex ? Or maybe >> a cache implementation ? >> > > Not sure how much this helps, but there was a Balisage talk by James > Fuller, titled "A catalog of Functional Programming idioms in XQuery 3.1" > <https://www.balisage.net/Proceedings/vol17/author-pkg/Fuller01/BalisageVol17-Fuller01.html>, > which produces (amongst others) a memoize function. It is written in the > Marklogic dialect of XQuery. but porting it was a no-brainer, since, AFAIR, > only the syntax for maps had to be changed. The Github repo is here > <https://github.com/xquery/xquery_functional_catalog/>. > > -- > Minden jót, all the best, Alles Gute, > Andreas Mixich > > > >

> It is written in the Marklogic dialect of XQuery. but porting it was a no-brainer, since, AFAIR, only the syntax for maps had to be changed. The Github repo is here.

De: "Christian Grün" <christian.gruen at gmail.com> À: "Andreas Mixich" <mixich.andreas at gmail.com>, "Mickael Desfrenes" <mickael.desfrenes at unicaen.fr> Cc: "basex-talk" <basex-talk at mailman.uni-konstanz.de> Envoyé: Mercredi 8 Avril 2020 11:05:46 Objet: Re: [basex-talk] Memoize Hi Mickael, hi Andreas, > It is written in the Marklogic dialect of XQuery. but porting it was a no-brainer, since, AFAIR, only the syntax for maps had to be changed. The Github repo is here. I see that the code uses MarkLogic’s map module functions, which are based on an implementation of a classical side-effecting and mutable hash map. As real XQuery maps are immutable (i.e., once defined, their contents will never change, see [1]), you may need to use Java bindings and instantiate a Java HashMap [2]. I have rewritten one of the proposed memoize functions, it’s attached. I forgot to mention that BaseX itself uses runtime optimizations to memoize data as well. Just two examples: 1. If a path expression is requested multiple times, its result will automatically be cached. In the query below, it’s //name that will only be evaluated once: //city[. = //name] 2. If large sequences are compared, the items to be compared will incrementally be stored in a hash map. In the query below, it’s the items of $lines2 that will be put to a hash map: let $lines1 := file:read-text-lines('file1.txt') let $lines2 := file:read-text-lines('file2.txt') return $lines1[. = $lines2] In both cases, evaluation time can be reduced from a quadratical to a linear runtime (and the result may be available within milliseconds instead of seconds or minutes). @Mickael: 1. Do you try to reduce the runtime of specific queries, or 2. do you want to get faster results if you run the same query multiple times? Do you possibly have specific use cases or queries which you’d like to speed up via memoization? Best, Christian [1] http://docs.basex.org/wiki/XQuery_3.1#Maps [2] http://docs.basex.org/wiki/Java_Bindings

On Thu, 2020-04-09 at 10:08 +0200, Mickael Desfrenes wrote: > > My goal was to get faster results when a query is run multiple times. > Yes, that's probably premature optimization, but since I do require > these things in other application stacks I thought I'd ask.

Am 08.04.2020 um 11:05 schrieb Christian Grün: > I see that the code uses MarkLogic’s map module functions, which are > based on an implementation of a classical side-effecting and mutable > hash map. As real XQuery maps are immutable (i.e., once defined, their > contents will never change, see [1]), you may need to use Java > bindings and instantiate a Java HashMap [2]. I have rewritten one of > the proposed memoize functions, it’s attached.