Re: absolute function
- Posted by mattlewis (admin) Mar 18, 2011
- 3833 views
Thank you for the replies and conclusions.
1. It is generally thought that a loop is costly in time, compared to a straight one line solution. On the other hand compiled executable have narrowed down the time for looping.
That's true, although there's more to it. Unless you have some way to do vector operations (GPU) or smartly parallelize the work, there are still loops. In this case, the loop is in the back end of the interpreter instead of user code. So there is some efficiency there. However, let's look at the code:
SubProgram [/home/matt/eu/test/abs.ex-newabs:00146] [s:148]
STACK SPACE: 5
Required: 5
[/home/matt/eu/test/abs.ex:2] (2)
1: 013 148 150 151 # MULTIPLY: [s:148], [LIT -2:150] => [_temp_:151]
5: 001 148 143 152 # LESS: [s:148], [LIT 0:143] => [_temp_:152]
9: 013 151 152 153 # MULTIPLY: [_temp_:151], [_temp_:152] => [_temp_:153]
13: 011 148 153 154 # PLUS: [s:148], [_temp_:153] => [_temp_:154]
17: 208 151 # DEREF_TEMP: [_temp_:151]
19: 208 152 # DEREF_TEMP: [_temp_:152]
21: 208 153 # DEREF_TEMP: [_temp_:153]
23: 028 146 147 154 # RETURNF: [_temp_:154] block[147]
27: 043 # BADRETURNF:
End SubProgram [newabs:00146]
Operations at 1, 5, 9 and 13 operate on each element of a sequence. Therefore, you have 4*n operations to complete. In the std/math.e implementation, we loop through once, at somewhat less efficiency, also including recursive calls, which take some time.
So there is a bit of a tradeoff. Here is the std/math.e version:
SubProgram [/home/matt/eu/test/abs.ex-stdabs:00164] [a:166]
STACK SPACE: 13
Required: 13
[/home/matt/eu/test/abs.ex:16] (16)
1: 067 166 169 # IS_AN_ATOM: [a:166] [_temp_:169]
4: 020 169 24 # IF: [_temp_:169] = 0 goto 0024
[/home/matt/eu/test/abs.ex:17] (17)
7: 103 166 143 17 # GREATEREQ_IFW [a:166] > [LIT 0:143] goto 0011 else goto 0017
[/home/matt/eu/test/abs.ex:18] (18)
11: 028 164 165 166 # RETURNF: [a:166] block[165]
[/home/matt/eu/test/abs.ex:19] (19)
15: 023 24 # ELSE goto 0024
[/home/matt/eu/test/abs.ex:20] (20)
17: 012 166 173 # UMINUS: [a:166] => [_temp_:173]
20: 028 164 165 173 # RETURNF: [_temp_:173] block[165]
[/home/matt/eu/test/abs.ex:23] (23)
24: 042 166 176 # LENGTH: [a:166] => [_temp_:176]
27: 125 142 176 142 164 175 79 # FOR_I: inc [LIT 1:142], lim [_temp_:176], initial [LIT 1:142],
# lv [i:175], jmp 0079
[/home/matt/eu/test/abs.ex:24] (24)
34: 092 166 175 167 # RHS_SUBS_CHECK: [a:166] sub [i:175] => [t:167]
[/home/matt/eu/test/abs.ex:25] (25)
38: 067 167 179 # IS_AN_ATOM: [t:167] [_temp_:179]
41: 020 179 59 # IF: [_temp_:179] = 0 goto 0059
[/home/matt/eu/test/abs.ex:26] (26)
44: 102 167 143 74 # IFW [t:167] < [LIT 0:143] goto 0048 else goto 0074
[/home/matt/eu/test/abs.ex:27] (27)
48: 012 167 182 # UMINUS: [t:167] => [_temp_:182]
51: 084 166 175 182 # ASSIGN_SUBS_CHECK: [a:166], [i:175] <= [_temp_:182]
55: 208 182 # DEREF_TEMP: [_temp_:182]
[/home/matt/eu/test/abs.ex:29] (29)
57: 023 74 # ELSE goto 0074
[/home/matt/eu/test/abs.ex:30] (30)
59: 018 167 184 # [t:167] => [_temp_:184]
62: 027 164 184 185 # FUNC: [stdabs:164][_temp_:184] => [_temp_:185]
66: 084 166 175 185 # ASSIGN_SUBS_CHECK: [a:166], [i:175] <= [_temp_:185]
70: 208 184 # DEREF_TEMP: [_temp_:184]
72: 208 185 # DEREF_TEMP: [_temp_:185]
[/home/matt/eu/test/abs.ex:32] (32)
74: 054 34 176 175 142 # ENDFOR_INT_UP1: top 0034, lim: [_temp_:176], lv [i:175], inc
# [LIT 1:142]
[/home/matt/eu/test/abs.ex:33] (33)
79: 028 164 165 166 # RETURNF: [a:166] block[165]
83: 043 # BADRETURNF:
End SubProgram [stdabs:00164]
In the case of just an atom, it looks faster (I haven't tested in detail). And in the case of sequences, larger sequences give larger penalties for sequence arithmetic.
4. I could quote a thousand APL v. Basic (straight line solutions v. looping and branching) and by and large the APL solutions were better in terms of speed, space used, etc. However, this is a Euphoria forum and I don't want to bring in those very old arguments, and other languages.
One of the interesting things about euphoria is how it performs relative to other languages. User code tends to be a lot more efficient in many ways, so penalties that other interpreted languages might incur as far as loops and that sort of thing aren't necessarily the bottleneck to the same extent.
Of course, compiled languages sometimes do a lot better, especially if they are smart about parallelizing things like this.
6. Resistance to change has been the downfall of many civilizations.
I think you'll find that improved performance is rarely resisted around here. However, as you've discovered, abs() has a rich history of performance tests and trials. 
Matt
