Topic: Single dimensional list to duoble dimensional

[irneb]

Never too late  :pissed:

I've had to rename yours to gbn2, since there was a gbn already:

Code: [Select]

Benchmarking ...........Elapsed milliseconds / relative speed for 256 iteration(s):

    (LIST-GBN LST 5)...................1232 / 2.55 <fastest>
    (GBN_1_EV LST 5)...................1294 / 2.42
    (GROUPBYNUM_MAC3 LST 5)............1763 / 1.78
    (LIST-GROUP-STEPREVERSE LST 5).....1794 / 1.75
    (GROUPBYNUM_MAC4 LST 5)............2590 / 1.21
    (LIST-GROUP LST 5).................2621 / 1.2
    (_SUBLISTS LST 5)..................2652 / 1.18
    (GBN2 LST 5).......................3027 / 1.04
    (LM:GROUPBYNUM-R LST 5)............3120 / 1.01
    (LM:GROUPBYNUM LST 5)..............3136 / 1
    (GBN LST 5)........................3136 / 1 <slowest>Not bad ... made the top 10!

Strange though, I did the previous test on another PC. Used the exact same test case:

Code: [Select]

(setq lst nil n 0)
(repeat 5000 (setq lst (cons n lst) n (1+ n)))The two PC's are extremely close to being identical (both i7-2600, both 16GB ram, both Win7 Pro, both Vanilla 2012). Yet there's some discrepancies in the benchmarking. I've run the benchmarking 5 times now and get similar results each time. Must be something strange running on the background in one but not the other.

Perhaps my AV, the 1st had ClamWin+MSSE, this one's got Avast!

[VovKa]

it's time to test all these compiled
you'll be surprised 

[irneb]

Yes, that would probably make a lot of difference!

Uncompiled (Interpreted):

Code: [Select]

Benchmarking ............Elapsed milliseconds / relative speed for 512 iteration(s):

    (LIST-GBN LST 5)............1029 / 3.5 <fastest>
    (GBN_1_EV LST 5)............1233 / 2.92
    (GROUPBYNUM_MAC4 LST 5).....2090 / 1.72
    (GROUPBYNUM_MAC3 LST 5).....2184 / 1.65
    (LIST-GBN2 LST 5)...........2386 / 1.51
    (LM:GROUPBYNUM-R LST 5).....2605 / 1.38
    (SPLIT LST 5)...............2636 / 1.37
    (WIZ-GRP LST 5).............2793 / 1.29
    (_SUBLISTS LST 5)...........2823 / 1.28
    (GROUPITEMS LST 5)..........2871 / 1.26
    (LM:GROUPBYNUM LST 5).......2964 / 1.22
    (LIST-GROUP-STEP LST 5).....2964 / 1.22
    (GROUPBYNUM_MAC2 LST 5).....3229 / 1.12
    (GROUPBYNUM_MAC LST 5)......3323 / 1.08
    (GBN2 LST 5)................3604 / 1 <slowest>
Compiled to FAS using Standard compilation:

Code: [Select]

Benchmarking .............Elapsed milliseconds / relative speed for 1024 iteration(s):

    (LIST-GBN LST 5)............1919 / 3.83 <fastest>
    (LM:GROUPBYNUM-R LST 5).....1950 / 3.77
    (LIST-GROUP-STEP LST 5).....1965 / 3.74
    (LM:GROUPBYNUM LST 5).......1966 / 3.74
    (GROUPBYNUM_MAC2 LST 5).....1981 / 3.71
    (GBN_1_EV LST 5)............2013 / 3.65
    (GBN2 LST 5)................2137 / 3.44
    (_SUBLISTS LST 5)...........2153 / 3.41
    (LIST-GBN2 LST 5)...........2293 / 3.2
    (GROUPBYNUM_MAC4 LST 5).....2745 / 2.68
    (GROUPBYNUM_MAC3 LST 5).....2933 / 2.5
    (GROUPITEMS LST 5)..........3245 / 2.26
    (SPLIT LST 5)...............3978 / 1.85
    (WIZ-GRP LST 5).............4118 / 1.78
    (GROUPBYNUM_MAC LST 5)......7347 / 1 <slowest>
Compiled to FAS using optimize & indirect linking:

Code: [Select]

Benchmarking .............Elapsed milliseconds / relative speed for 1024 iteration(s):

    (LIST-GBN LST 5)............1934 / 3.19 <fastest>
    (LM:GROUPBYNUM-R LST 5).....1966 / 3.14
    (GROUPBYNUM_MAC2 LST 5).....1981 / 3.12
    (LM:GROUPBYNUM LST 5).......1981 / 3.12
    (LIST-GROUP-STEP LST 5).....1997 / 3.09
    (GBN_1_EV LST 5)............2028 / 3.05
    (GBN2 LST 5)................2153 / 2.87
    (_SUBLISTS LST 5)...........2153 / 2.87
    (LIST-GBN2 LST 5)...........2309 / 2.68
    (GROUPBYNUM_MAC4 LST 5).....2777 / 2.22
    (GROUPBYNUM_MAC3 LST 5).....2901 / 2.13
    (GROUPITEMS LST 5)..........3260 / 1.9
    (SPLIT LST 5)...............3526 / 1.75
    (WIZ-GRP LST 5).............3713 / 1.66
    (GROUPBYNUM_MAC LST 5)......6178 / 1 <slowest>
And lastly, FAS with optimized & linked directly:

Code: [Select]

Benchmarking ..............Elapsed milliseconds / relative speed for 2048 iteration(s):

    (GROUPBYNUM_MAC2 LST 5)......1903 / 5.89 <fastest>
    (LIST-GROUP-STEP LST 5)......1935 / 5.79
    (LM:GROUPBYNUM LST 5)........1950 / 5.74
    (LM:GROUPBYNUM-R LST 5)......2012 / 5.57
    (GBN2 LST 5).................2309 / 4.85
    (GROUPBYNUM_MAC4 LST 5)......2324 / 4.82
    (_SUBLISTS LST 5)............2356 / 4.75
    (LIST-GBN2 LST 5)............2387 / 4.69
    (GROUPBYNUM_MAC3 LST 5)......2449 / 4.57
    (GROUPITEMS LST 5)...........2668 / 4.2
    (SPLIT LST 5)................3463 / 3.23
    (LIST-GBN LST 5).............3697 / 3.03
    (WIZ-GRP LST 5)..............4399 / 2.55
    (GBN_1_EV LST 5).............4493 / 2.49
    (GROUPBYNUM_MAC LST 5)......11201 / 1 <slowest>
Quite a lot of discrepancy isn't there? Here's the test code:

Code - Auto/Visual Lisp: [Select]

1. (setq funcs '(LIST-GBN2 GBN2 LIST-GBN GROUPITEMS GROUPBYNUM_MAC4 GBN_1_EV WIZ-GRP SPLIT GROUPBYNUM_VK GROUPBYNUM_MAC3 GROUPBYNUM_MAC2 GROUPBYNUM_MAC
2.     LIST-GROUP _SUBLISTS LM:GROUPBYNUM-R LM:GROUPBYNUM LIST-GROUP-STEPREVERSE LIST-GROUP-IDX LIST-GROUP-STEP))
3. (setq lst nil n 0)
4. (repeat 5000 (setq lst (cons n lst) n (1+ n)))
5. (load "list-group.lsp")
6. (benchmark (mapcar '(lambda (f) (cons f '(lst 5)))
7.                    (vl-remove-if-not
8.                      '(lambda (f) (equal (apply f (list '(1 2 3 4 5 6 7 8 9 0) 5)) '((1 2 3 4 5) (6 7 8 9 0))))
9.                      funcs)))
10. (vlisp-compile 'st "list-group.lsp" "list-group-st.fas")
11. (load "list-group-st.fas")
12. (benchmark (mapcar '(lambda (f) (cons f '(lst 5)))
13.                    (vl-remove-if-not
14.                      '(lambda (f) (equal (apply f (list '(1 2 3 4 5 6 7 8 9 0) 5)) '((1 2 3 4 5) (6 7 8 9 0))))
15.                      funcs)))
16. (vlisp-compile 'lsm "list-group.lsp" "list-group-lsm.fas")
17. (load "list-group-lsm.fas")
18. (benchmark (mapcar '(lambda (f) (cons f '(lst 5)))
19.                    (vl-remove-if-not
20.                      '(lambda (f) (equal (apply f (list '(1 2 3 4 5 6 7 8 9 0) 5)) '((1 2 3 4 5) (6 7 8 9 0))))
21.                      funcs)))
22. (vlisp-compile 'lsa "list-group.lsp" "list-group-lsa.fas")
23. (load "list-group-lsa.fas")
24. (benchmark (mapcar '(lambda (f) (cons f '(lst 5)))
25.                    (vl-remove-if-not
26.                      '(lambda (f) (equal (apply f (list '(1 2 3 4 5 6 7 8 9 0) 5)) '((1 2 3 4 5) (6 7 8 9 0))))
27.                      funcs)))

There were some warnings in the compiling output, so I added a check to omit any functions not performing correctly. Also to make the benchmark not have to run for days, I've omitted those just taking too long 

[Lee Mac]

Sorry to burst the bubble on your extensive testing Irneb, but you didn't rename the recursive call in my 'LM:GroupByNum-R' function, and my 'GroupByNum_Mac2' function is the same as the iterative 'LM:GroupByNum' function I posted on my site 

[irneb]

Just realized as I was trying to make a benchmark when VLIDE was not loaded. Anyhow, that wasn't the only mistakes  :ugly:

Sorry guys! Here's the benchmarking on a clean start of ACAD:

Command: (load "Benchmark")
BENCHMARK

Command: (load "BenchTest")
Elapsed milliseconds / relative speed for 1024 iteration(s):

    (LIST-GBN LST 5)............1591 / 3.84 <fastest>
    (GBN_1_EV LST 5)............1654 / 3.7
    (LIST-GBN2 LST 5)...........2434 / 2.51
    (LIST-GROUP-STEP LST 5).....2667 / 2.29
    (GROUPBYNUM_MAC2 LST 5).....2684 / 2.28
    (LM:GROUPBYNUM LST 5).......2715 / 2.25
    (GROUPBYNUM_MAC LST 5)......2776 / 2.2
    (GBN2 LST 5)................2823 / 2.17
    (GROUPBYNUM_MAC4 LST 5).....2855 / 2.14
    (LM:GROUPBYNUM-R LST 5).....2870 / 2.13
    (GROUPBYNUM_MAC3 LST 5).....2948 / 2.07
    (_SUBLISTS LST 5)...........3214 / 1.9
    (GROUPITEMS LST 5)..........3245 / 1.88
    (SPLIT LST 5)...............3744 / 1.63
    (WIZ-GRP LST 5).............3806 / 1.61
    (GROUPBYNUM_VK LST 5).......6115 / 1 <slowest>
Elapsed milliseconds / relative speed for 1024 iteration(s):

    (LIST-GBN LST 5)............1560 / 4.14 <fastest>
    (GBN_1_EV LST 5)............1591 / 4.06
    (GROUPBYNUM_MAC2 LST 5).....1762 / 3.67
    (LIST-GROUP-STEP LST 5).....1778 / 3.63
    (LM:GROUPBYNUM LST 5).......1779 / 3.63
    (_SUBLISTS LST 5)...........1919 / 3.37
    (GBN2 LST 5)................1934 / 3.34
    (LM:GROUPBYNUM-R LST 5).....2043 / 3.16
    (LIST-GBN2 LST 5)...........2075 / 3.11
    (GROUPBYNUM_MAC LST 5)......2075 / 3.11
    (GROUPBYNUM_MAC4 LST 5).....2574 / 2.51
    (GROUPBYNUM_MAC3 LST 5).....2637 / 2.45
    (GROUPITEMS LST 5)..........2949 / 2.19
    (WIZ-GRP LST 5).............3432 / 1.88
    (SPLIT LST 5)...............3495 / 1.85
    (GROUPBYNUM_VK LST 5).......6458 / 1 <slowest>
Elapsed milliseconds / relative speed for 1024 iteration(s):

    (GBN_1_EV LST 5)............1592 / 3.95 <fastest>
    (LIST-GBN LST 5)............1607 / 3.91
    (GROUPBYNUM_MAC2 LST 5).....1763 / 3.57
    (LM:GROUPBYNUM LST 5).......1763 / 3.57
    (LIST-GROUP-STEP LST 5).....1778 / 3.54
    (_SUBLISTS LST 5)...........1919 / 3.28
    (GBN2 LST 5)................2028 / 3.1
    (GROUPBYNUM_MAC LST 5)......2059 / 3.05
    (LM:GROUPBYNUM-R LST 5).....2059 / 3.05
    (LIST-GBN2 LST 5)...........2433 / 2.58
    (GROUPBYNUM_MAC4 LST 5).....2574 / 2.44
    (GROUPBYNUM_MAC3 LST 5).....2667 / 2.36
    (GROUPITEMS LST 5)..........3011 / 2.09
    (SPLIT LST 5)...............3338 / 1.88
    (WIZ-GRP LST 5).............3432 / 1.83
    (GROUPBYNUM_VK LST 5).......6287 / 1 <slowest>
Elapsed milliseconds / relative speed for 2048 iteration(s):

    (GROUPBYNUM_MAC2 LST 5).....1591 / 2.96 <fastest>
    (LM:GROUPBYNUM LST 5).......1591 / 2.96
    (LIST-GROUP-STEP LST 5).....1623 / 2.9
    (_SUBLISTS LST 5)...........1966 / 2.4
    (GBN2 LST 5)................1997 / 2.36
    (LIST-GBN2 LST 5)...........2060 / 2.29
    (GROUPBYNUM_MAC4 LST 5).....2106 / 2.24
    (LM:GROUPBYNUM-R LST 5).....2106 / 2.24
    (GROUPBYNUM_MAC3 LST 5).....2137 / 2.2
    (GROUPBYNUM_MAC LST 5)......2137 / 2.2
    (GROUPITEMS LST 5)..........2340 / 2.01
    (LIST-GBN LST 5)............3042 / 1.55
    (GBN_1_EV LST 5)............3104 / 1.52
    (SPLIT LST 5)...............3183 / 1.48
    (WIZ-GRP LST 5).............3619 / 1.3
    (GROUPBYNUM_VK LST 5).......4711 / 1 <slowest>

[VovKa]

    (GROUPBYNUM_MAC2 LST 5).....1591 / 2.96 <fastest>
    (LM:GROUPBYNUM LST 5).......1591 / 2.96
    (LIST-GROUP-STEP LST 5).....1623 / 2.9
    (_SUBLISTS LST 5)...........1966 / 2.4
    (GBN2 LST 5)................1997 / 2.36
    (LIST-GBN2 LST 5)...........2060 / 2.29
    (GROUPBYNUM_MAC4 LST 5).....2106 / 2.24
    (LM:GROUPBYNUM-R LST 5).....2106 / 2.24
    (GROUPBYNUM_MAC3 LST 5).....2137 / 2.2
    (GROUPBYNUM_MAC LST 5)......2137 / 2.2
    (GROUPITEMS LST 5)..........2340 / 2.01
    (LIST-GBN LST 5)............3042 / 1.55
    (GBN_1_EV LST 5)............3104 / 1.52
    (SPLIT LST 5)...............3183 / 1.48
    (WIZ-GRP LST 5).............3619 / 1.3
    (GROUPBYNUM_VK LST 5).......4711 / 1 <slowest>

you can't fool the compiler
as soon as we are going to use/sell lsa-compiled applications we'd better stick to simple 'basic' loops

[irneb]

Yes, it seems that way doesn't it. Recursion doesn't seem to gain anything by compiling, and even less for those self-modifying functions of Evgeniy and myself. That's why I wrote the list-gbn2 - it basically uses the same idea, but places it inside a repeat loop and cond statement - instead of generating a defun on the fly. It doesn't help too much though, with the direct linking it seems that a cddddr doesn't perform better than a repetition of cdr - and the overhead required to test if four repetitions can be combined into one makes for a less efficient loop. I think that's why it doesn't gain as much as the other looping algorithms.

Still, it's only if you go the direct linking way when the speed of those self-modifying code is nullified. See in the other 2 types of compilation - the normal looping algorithms only just reach the same speed (i.e. 2-3 times faster).

So I guess it's a situation of your deliverable. Are you going to compile it? If so can you use direct linking? If only interpreted I'd definitely go for the self-modifiers, otherwise I'd go with Lee's iterative method.