Re: [fricas-devel] [PATCH] make new$List faster
oldk1331 wrote: > > > Also, there is tricky balance > > between speed and code size: for rarely executed code > > the main cost is reading it from RAM and evicting > > from cache more useful code. That can negate gains > > from faster execution. > > Well, MAKELIST$Lisp is surely most RAM efficient and > fastest. I was probably unclear: code size matters in case of list comprehension because each use is a separate copy of a template and there are a lot of uses in the algebra. Also, on my machine the following version: new(n, e) == res := empty() for i in 1..n repeat res := cons(e, res) res which produces result in "reverse" order for long lists has the same speed (within measurement noise) as MAKELIST version. For short list it may be faster, because 'make-list' probably have few extra instructions to parse keyword arguments. Concerning RAM efficient: the version above is probably of smaller than 'make-list'. Of course 'make-list' is already contained in Lisp image, but code that we do not use at all is cheap: there is resonable chance that it will live only on disc and almost surely will not get into caches. > I want to know when it's worth to introduce a > Lisp function instead of implement it in Spad? Well some Lisp functions are "primitives", they offer functionalty which is not available in other way. Of course we need them. Then there are functions which we introduce for performance. In particular Spad compiler will only inline functions which have single Lisp expression as implementation. So if some operation should be inlined it has to be implemented via call to Lisp macro/function. Now, basically all functions could get some speedup by providing optimized Lisp implementation. But if you look at hand-written Lisp code you will see that most is less optimized than code generated by Spad compiler. Simply most of code is not performance critical. So for most code clarity and correctness are much more important. Now, for typical Spad programmer Lisp code is an opaque blob and hence less clear than Spad code. So write in Spad unless you have strong reason to use Lisp. That is there is significant speed gain or using Lisp function say saves effort to rewrite some substaial piece of code. Note: speed gain of 10% in rarely used function is insignifcant. Gain of 10% in freqently used function is worthwile, but it is not always clear if gain is real and robust. That is there may be gain on benchmarks but no gain (or even loss) in real use. As an example, in the past two dimensional Spad arrays were implemented as PrimitiveArray of PrimitiveArray-s and element accessors were Spad functions. Replacing Spad code by Lisp macros gave about 20 times faster array accessors. Given that array accessors are frequently used in inner loops this was a clear gain. -- Waldek Hebisch -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
Re: [fricas-devel] [PATCH] make new$List faster
> Also, there is tricky balance > between speed and code size: for rarely executed code > the main cost is reading it from RAM and evicting > from cache more useful code. That can negate gains > from faster execution. Well, MAKELIST$Lisp is surely most RAM efficient and fastest. I want to know when it's worth to introduce a Lisp function instead of implement it in Spad? -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
Re: [fricas-devel] [PATCH] make new$List faster
oldk1331 wrote: > > BTW2: If you are worried that [...] is slower than > > MAKELIST you should rather work on increasing speed > > of list comprehesion (that is []). Current > > version constructs list in reverse order and then > > destructively reverses the result. > > It is possible to avoid the NREVERSE call? > Unless you do it by recursion and risk the stack > to explode? Well, for 'new' formally the final NREVERSE is not needed at all since all nodes have the same value. In general there is well-know imperative idiom: after creating next node one updates previous node. Essentially: new(n, e) == e0 := empty() n = 0 => e0 res := cons(e, e0) old := res for i in 2..n repeat new := cons(e, old) setrest!(old, new) new := old res As you see the code is longer than version working in reverse. For long list avoidning second scan should give small win. For short lists (most important case) that is more tricky: one needs to make sure that the code (in particular loop setup) is well optimized to have any gain. Also, there is tricky balance between speed and code size: for rarely executed code the main cost is reading it from RAM and evicting from cache more useful code. That can negate gains from faster execution. -- Waldek Hebisch -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
Re: [fricas-devel] [PATCH] make new$List faster
> BTW: 'new' for lists exists mainly because of generic > interface. However normally after 'new' aggregate > is modified. In case of lists in almost all cases it > will be more efficient to create list in incremental way > using desired values instead of modification. You do have a point, I briefly checked there's not many usage of new$List. > BTW2: If you are worried that [...] is slower than > MAKELIST you should rather work on increasing speed > of list comprehesion (that is []). Current > version constructs list in reverse order and then > destructively reverses the result. It is possible to avoid the NREVERSE call? Unless you do it by recursion and risk the stack to explode? What's your opinion on removing IndexedList? -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
Re: [fricas-devel] [PATCH] make new$List faster
> > I tested with "a := new(2*10^7,2)$List INT;", and before > each call, I do a ")lisp (SB-EXT:GC)" to avoid GC during > benchmarking. > > MAKELIST takes 0.29~0.33s, the loop takes 0.34~0.39s. IMO it is not worth calling Lisp functions for rather small gain. BTW: 'new' for lists exists mainly because of generic interface. However normally after 'new' aggregate is modified. In case of lists in almost all cases it will be more efficient to create list in incremental way using desired values instead of modification. BTW2: If you are worried that [...] is slower than MAKELIST you should rather work on increasing speed of list comprehesion (that is []). Current version constructs list in reverse order and then destructively reverses the result. It means that list have to be traversed two times. For short list second traversal is very fast because list is in cache. But for long lists we pay cost of reading it from RAM (you have 32 MB of data which almost surely is bigger than largest cache in your machine). -- Waldek Hebisch -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
Re: [fricas-devel] [PATCH] make new$List faster
I tested with "a := new(2*10^7,2)$List INT;", and before each call, I do a ")lisp (SB-EXT:GC)" to avoid GC during benchmarking. MAKELIST takes 0.29~0.33s, the loop takes 0.34~0.39s. -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
Re: [fricas-devel] [PATCH] make new$List faster
oldk1331 wrote: > > > What is gain from this compared to: > > > > new(n, e) == [e for i in 1..n] > > It doesn't compile: Right, we need: new(n, e) == [e for i in 1..n]@List(S) pretend % -- Waldek Hebisch -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
Re: [fricas-devel] [PATCH] make new$List faster
> What is gain from this compared to: > > new(n, e) == [e for i in 1..n] It doesn't compile: compiling exported new : (NonNegativeInteger,S) -> $ ** comp fails at level 1 with expression: ** error in function new ((COLLECT (STEP |i| 1 1 |n|) |e|)) ** level 1 ** $x:= (COLLECT (STEP i (One) 1 n) e) $m:= $ $f:= |e| # . #1=#) (|n| # . #2=#) (|e| . #1#) (|n| . #2#) ...))) >> Apparent user error: Invalid collect bodytype -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
Re: [fricas-devel] [PATCH] make new$List faster
oldk1331 wrote: > > new$List calls Lisp function directly, instead of repeatedly > calling "concat". > > This change and the previous map! change probably > should go into IndexedList, but I really think we should > remove IndexedList : > > 1. It's not used anywhere beside List. (And probably > nobody uses it.) > 2. Unlike arrays, index (elt) is O(n) for lists, so for performance > reasons, nobody should use index in loops, they should > use "rest". > > diff --git a/src/algebra/list.spad b/src/algebra/list.spad > index dcebdb2..e53b314 100644 > --- a/src/algebra/list.spad > +++ b/src/algebra/list.spad > @@ -250,6 +250,7 @@ > > Implementation ==> > IndexedList(S, LISTMININDEX) add > + new(n, e) == MAKELIST(n, e)$Lisp >nil()== empty() >null l == empty?(l) >cons(s, l) == concat(s, l) What is gain from this compared to: new(n, e) == [e for i in 1..n] -- Waldek Hebisch -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
[fricas-devel] [PATCH] make new$List faster
new$List calls Lisp function directly, instead of repeatedly calling "concat". This change and the previous map! change probably should go into IndexedList, but I really think we should remove IndexedList : 1. It's not used anywhere beside List. (And probably nobody uses it.) 2. Unlike arrays, index (elt) is O(n) for lists, so for performance reasons, nobody should use index in loops, they should use "rest". diff --git a/src/algebra/list.spad b/src/algebra/list.spad index dcebdb2..e53b314 100644 --- a/src/algebra/list.spad +++ b/src/algebra/list.spad @@ -250,6 +250,7 @@ Implementation ==> IndexedList(S, LISTMININDEX) add + new(n, e) == MAKELIST(n, e)$Lisp nil()== empty() null l == empty?(l) cons(s, l) == concat(s, l) diff --git a/src/lisp/primitives.lisp b/src/lisp/primitives.lisp index 6cc8c84..bea6a6f 100644 --- a/src/lisp/primitives.lisp +++ b/src/lisp/primitives.lisp @@ -49,6 +49,10 @@ (defmacro ANCOLS (v) `(array-dimension (the (simple-array T (* *)) ,v) 1)) +;;; list creation +(defun MAKELIST (size init) +(make-list size :initial-element init)) + ;;; string accessors (defmacro STR_ELT(s i) -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
