Performance of loops

[Kurt Pagani]

The four functions f1..f4 below do all the same, calculating the number
of different integers of the form x^2+x*y+y^2 for (x,y) in [-n,n] x
[-n,n]. Only f4 (the lisp calls) performs reasonably.

Either I do something fundamentally wrong -- or Fricas does.
I was blaming SBCL in the first place, that's why I wrote f4.


For the backgroud of these calculations see my notes
https://github.com/nilqed/spadlib/blob/master/frustum/docs/perf.txt


https://github.com/nilqed/spadlib/blob/master/frustum/test/frustum0.input

Any clue?

---

f1(n:INT):INT ==
#removeDuplicates!(concat! [[x*x+x*y+y*y for x in -n..n|x<=y] for y
in -n..n])

f2(n:INT):INT ==
l:List INT:=[]
for x in -n..n repeat
for y in -n..n | y >= x repeat
l:=cons(x*x+x*y+y*y,l);
#removeDuplicates!(l)

f3(n:INT):INT ==
l:List INT:=[]
for x in -n..n repeat
for y in -n..n | y >= x repeat
l:=concat!(l,x*x+x*y+y*y);
#removeDuplicates!(l)


---
reval(s) ==> EVAL(READ_-FROM_-STRING(s)$Lisp)$Lisp

df:="(defun frustum (n)(remove-duplicates _
(apply #'append (loop for x from (- n) to n collect _
(loop for y from (- n) to n collect _
(+ (* x x) (* x y) (* y y)))))))"

reval(df)
---

f4(n:INT):INT == integer LENGTH(FRUSTUM(n)$Lisp)$Lisp


)set message time on

f1(100) --> Time: 0.37 (EV) + 0.02 (OT) = 0.39 sec
f2(100) --> Time: 0.29 (EV) = 0.30 sec
f3(100) --> Time: 4.01 (EV) + 0.05 (GC) = 4.06 sec
f4(100) --> Time: 0.07 (EV) = 0.07 sec

f1(250) --> Time: 10.26 (EV) = 10.26 sec
f2(250) --> Time: 10.26 (EV) = 10.26 sec
f3(250) --> Time: 157.82 (EV) + 2.64 (GC) = 160.46 sec
f4(250) --> Time: 0.41 (EV) + 0.01 (GC) = 0.42 sec

f1(500) --> Time: 163.73 (EV) = 163.73 sec
f2(500) --> Time: 165.17 (EV) = 165.17 sec
--f3(500) --> too long :( ctrl-c after 30min / don't use concat.
f4(500) --> Time: 1.63 (EV) + 0.25 (GC) = 1.87 sec


f4(1000) --> Time: 6.84 (EV) + 0.33 (GC) = 7.17 sec
f4(2000) --> Time: 29.35 (EV) + 2.35 (GC) = 31.70 sec
f4(3000) --> Time: 65.58 (EV) + 6.18 (GC) = 71.76 sec

-- 2793219 frustums in 6001^2=36012001 for n=3000.

[Qian Yun]

Without profiling, just from experience:

1. The bottleneck should be in removeDuplicates, it's O(n^2).

If sorted first, then remove consecutive duplicates, it will be
O(n*log(n)).

But we only have 'removeRepeats!' for array, not list.
Maybe we should add that.

2. Change from list to array should give constant factor boost.

3. Change from interpreter (.input) to compiler (.spad) should
give another boost. The interpreter list generation
([f x for x in seg]) is slow.


My one liner, with some room of improvement:

f5 n == # removeRepeats! sort! flexibleArray parts
matrix(2*n+1,2*n+1,(x:INT,y:INT):INT+->(x-1-n)^2+(y-1-n)^2+(x-1-n)*(y-1-n))

f5(3000) --> 24.84 sec

But for your f4 version, put the lisp code in a file and
')lisp (load (compile-file "tmp.lisp"))' on it,
for f4(3000) --> 9.49 sec. If not compile, it's 33.08 sec.

The lisp version has not used the sort and removeRepeats! trick.

- Qian

[Qian Yun]

More comments:

If you run my 'f5(3000)' directly, it will be very slow.

That's a bug I reported in 2018 Jan 17:
[BUG] first call to 'sort' is very slow

So you should run 'f5(1)' first to "cache" the call for 'sort'.


The problem with your f3 is that, 'concat!(l, x)' needs to
traverse the whole list to add a single element to the end of list,
you should use 'concat(x, l)' instead to add element to the beginning,
which makes it the same as f2.

- Qian

[Waldek Hebisch]

On Wed, Jul 15, 2026 at 01:22:42PM +0200, Kurt Pagani wrote:
> The four functions f1..f4 below do all the same, calculating the number of
> different integers of the form x^2+x*y+y^2 for (x,y) in [-n,n] x [-n,n].
> Only f4 (the lisp calls) performs reasonably.
>
> Either I do something fundamentally wrong -- or Fricas does.
> I was blaming SBCL in the first place, that's why I wrote f4.
>
>
> For the backgroud of these calculations see my notes
> https://github.com/nilqed/spadlib/blob/master/frustum/docs/perf.txt
>
>
> https://github.com/nilqed/spadlib/blob/master/frustum/test/frustum0.input
>
> Any clue?

1. Use sbcl profiler:

)lisp (sb-sprof:start-profiling)
-- do the computation
)lisp (sb-sprof:stop-profiling)
)lisp (sb-report)

There is some effort involved in reading reports and some part
may be misleading, but usully it helps a lot.

2. Boot flag '$reportOptimization' causes intepreter to print
generated Lisp code. Set it like

)boot $reportOptimization := true

and do your computation.

3. Interpreter frequently inserts runtime coercions. In such
case getting better type agreement or writing in Spad can help.

4. In HyperDoc you can find wich implementation is in use. Search
for List, give Integer as parameter, click on 'Operations', choose
'removeDuplicates!', click on 'Implementations'. It tells you
that 'removeDuplicates!' is implemented in List. Looking at code
in List shows quadratic loop. This is generic implementation,
without extra structure is to not possible to do better.

5. For mass removal of duplicates hash tables should be better.
You can try something like:

f2(n:INT):INT ==
t := empty()$Table(INT, Boolean)

for x in -n..n repeat
for y in -n..n | y >= x repeat

setelt!(t, x*x+x*y+y*y, true)
%keys(t)

You can also try 'XHashTable(INT, Boolean)' instead of 'Table'
(for Integer keys 'Table' probably is faster, but 'XHashTable'
can give you hash table in some cases where 'Table' gives
association list).

> ---
>
> f1(n:INT):INT ==
> #removeDuplicates!(concat! [[x*x+x*y+y*y for x in -n..n|x<=y] for y in
> -n..n])
>
> f2(n:INT):INT ==
> l:List INT:=[]
> for x in -n..n repeat
> for y in -n..n | y >= x repeat
> l:=cons(x*x+x*y+y*y,l);
> #removeDuplicates!(l)

Building list should be OK, but our 'removeDuplicates!' has quadratic
behaviour. Try 'REMOVE_-DUPLICATES(l)$Lisp' instead.

> f3(n:INT):INT ==
> l:List INT:=[]
> for x in -n..n repeat
> for y in -n..n | y >= x repeat
> l:=concat!(l,x*x+x*y+y*y);
> #removeDuplicates!(l)

That is know anypattern which causes quadratic behaviour. Appending
at the end means that function has to travel trough the list first.

--
Waldek Hebisch

[Kurt Pagani]

Thank you both, very enlightening!

Actually I was unaware of removeRepeats! in FlexibleArray.

Regarding the concat!: (%, S) -> %, it's obvious, however I'm wondering
whether a casual user ever thinks about such things.

> Try 'REMOVE_-DUPLICATES(l)$Lisp' instead.
Yes, indeed, this one should keep in mind!