1. Reverse() was: Win32Lib Update
- Posted by Hawke <mdeland at NWINFO.NET> Nov 28, 1998
- 469 views
Ralf Nieuwenhuijsen wrote: > Why not start a thread ? > function reverse_flat (sequence s) > sequence result > result = {} > for index = 1 to length(s) do > result = prepend(result, s[index]) > end for > return result > end function I'll jump in here :> y'all should know i cannae r'fuse a speed tweak :> let's try: func rev_flat(seq data) seq result int len, from len = length(data) from = len --i really could reuse len.... result = repeat(0,len) --BOOM, call alloc *once* for toindex = 1 to len do result[toindex] = data[from] from = from - 1 --and this takes 1 single tick... end for return result end func now, this (should be/is) faster than prepend... 1:im not having to worry about all that alloc, alloc even more, alloc even more AGAIN... etc... that prepend/append will do as it grows a new seq... yes, pre/append DOES alloc a little more... but, i have seen EU take a realllyyyy hard, long "think" in my fuzzy logic library on attempting to find a 'truth' while performing image recognition chores... this is how/why i found this method, and no, i haven't had time to update all of the fuzzy library to take advantage of this... someone once said on the list that repeat() doesn't work good on large sequence creation, like after a couple hundred thousand or so.... i never found that... has anyone??? 2: im only swapping pointers :) and, of course, recursing this would be easy.... func recurseREV(seq data) seq result int len, from object temp len = length(data) from = len result = repeat(0,len) for toindex = 1 to len do temp = data[from] if atom(temp) then result[toindex] = temp else result[toindex] = recurseREV(temp) end if from = from - 1 end for return result end func so... who gonna bncmrk??? :) ta! --Hawke'
2. Re: Reverse() was: Win32Lib Update
- Posted by Ralf Nieuwenhuijsen <nieuwen at XS4ALL.NL> Nov 28, 1998
- 439 views
Hawke suggested: >now, this (should be/is) faster than prepend... >1:im not having to worry about all that alloc, >alloc even more, alloc even more AGAIN... etc... >that prepend/append will do as it grows a new seq... As I recall, an append/prepend as only statement in a for-block will be optimized to one alloc, one pass proccesing. >yes, pre/append DOES alloc a little more... but, >i have seen EU take a realllyyyy hard, long "think" >in my fuzzy logic library on attempting to find a >'truth' while performing image recognition chores... You were prolly appending/prepending to an sliced/indexed sequence. All optimization fails at this point: result, for every append/prepend, it reallocates a sequence of the new length, copies the old sequence, copies the new part, frees the old sequence. And yes, this is sloooww indeed. >someone once said on the list that repeat() doesn't >work good on large sequence creation, like after a >couple hundred thousand or so.... i never found that... >has anyone??? Me neither. >so... who gonna bncmrk??? Maybe later today.. still working on my new graphical botmatch routines.. Ralf
3. Re: Reverse() was: Win32Lib Update
- Posted by Hawke <mdeland at NWINFO.NET> Nov 28, 1998
- 435 views
Ralf Nieuwenhuijsen wrote: > Hawke suggested: > >now, this (should be/is) faster than prepend... > >1:im not having to worry about all that alloc, > >alloc even more, alloc even more AGAIN... etc... > >that prepend/append will do as it grows a new seq... > As I recall, an append/prepend as only statement in a for-block will be > optimized to one alloc, one pass proccesing. errrrr.... i really don't think so.... see irv's benchmarks... ummmm.... the prepend came in last... :/ i could make mine go even faster, especially for large iterations of piddly sized sequences (like the one thrown at it in the benchmark...) the newer, tweaked just a little more (alot for large iteration/small sequences) is: func rev(seq data) int junk seq result junk = length(data) for from = 1 to junk do result[from] = data[junk] junk = junk - 1 end for return result end func i just saved 100000 clock ticks for irv's bnchmrk... not shabby... a million length seq? saved 1000000 clock ticks... the reason this came in second to mine is: x = length(s) r = repeat(0,x) for i = 1 to x do r[i] = s[x-i+1] --right here, you blew 100000 ticks... end for --million length? 1000000 ticks... return r > >yes, pre/append DOES alloc a little more... but, > >i have seen EU take a realllyyyy hard, long "think" > >in my fuzzy logic library on attempting to find a > >'truth' while performing image recognition chores... > You were prolly appending/prepending to an sliced/indexed sequence. All > optimization fails at this point: result, for every append/prepend, it > reallocates a sequence of the new length, copies the old sequence, copies > the new part, frees the old sequence. And yes, this is sloooww indeed. actually, i was doing nearly exactly what you were... to wit: you have a pair of sequences... indicies matching element for element... you want to know the minimum value at each index and grab that element... a={10,20,10,0,10,20} b={20,20,10,20,0,10} u have min() func min (atom a, atom b) if a>b then a=b end if return a end func (its faster than the one by carl for large seq...) so.... i tried this first... it's what u are suggesting, a one statment for block... func one(seq: l1, l2) seq r r={} for i = 1 to length(l1) do r = r & min(l1,l2) end for return r end func and.... it's slowwwww... throw a few 800x600x16.7M images at it... u snore... (remembering to adjust for each pixel being a length3 seq) i then did: func two(seq l1,l2) int len seq r len = length(l1) r = repeat(0,len) for i = 1 to len do r[i] = min(l1,l2) end for return i end for and i began clocking decent speeds.... *shrug*... i wouldn't have offered my observations about this pre/appending issue had i not watched EU suddenly BOG when i went over about a 400x400x16.7M image.... i was clocking what i thought were good timings in the fuzzy logic computations... i tried a 100x100x1 sequence... flew along, had to do a couple thousand iterations to build up to a second... went to 200x200x1... roughly doubled time... 300x300x1.. still no worries... started working on really bigXfew iterations.... 1000000x1... clipped along... 100000x10... no worries... etc... then reversed that... really smallXlots iterations... 10x10000... no prob... 100x1000... zoom... so i said... lets go truecolor... 100x100x3 was bout 3 times as long as 100x100x1... took like a second... 200x200x3 was bout 5 (i think..., these numbers don't need to be accurate, because it was the relationship of the values that will bear out in a moment) and 300x300x3 was.. mebbe a minute... i hit 400x400x3 (or so...) and **WHAM** i went, got coffee, came back, smoked a cig, came back, ... nada... it took like 15 minutes... just out of nowhere... shoulda been ...ohhh... maybe 3 minutes *tops* so i said this won't do... and found the problem to be appending/prepending... once i started playing the shuffle pointer game, it smoothed out and its a pretty fast library as a result of the extensive benchmarking i did on this issue... hope this helps someone... --Hawke'
4. Re: Reverse() was: Win32Lib Update
- Posted by Ralf Nieuwenhuijsen <nieuwen at XS4ALL.NL> Nov 28, 1998
- 422 views
>> As I recall, an append/prepend as only statement in a for-block will be >> optimized to one alloc, one pass proccesing. >errrrr.... i really don't think so.... >see irv's benchmarks... >ummmm.... the prepend came in last... :/ ;-( Robert, said append and prepend were like, really really optimized. And for-statements as well.. So, Robert (or Junko now it seems again, could there be some 'extra' optimization with statement blocks like for- and while- . Esspecially when they contain only one statement. (which should be fairly easy to optimize). But I was also thinking of multiple 'slices'/'indexes' to be looked up only once, within a statement block. And off couse the "for each item in my-sequence do" - syntax provides both optimization 'oppertunities' as well as increased error checking, and more readable code. Ralf
5. Re: Reverse() was: Win32Lib Update
- Posted by Daniel Berstein <daber at PAIR.COM> Nov 28, 1998
- 434 views
My attemp: function reverse(object data) object aux integer midway if sequence(data) then midway = floor(length(data) / 2) if midway != (length(data) / 2) then for index = 1 to midway do aux = reverse(data[index]) data[index] = reverse(data[(midway*2) - index + 2]) data[(midway*2) - index + 2] = aux end for data[midway+1] = reverse(data[midway+1]) else for index = 1 to midway do aux = reverse(data[index]) data[index] = reverse(data[(midway*2) - index + 1]) data[(midway*2) - index + 1] = aux end for end if end if return data end function I'm no speed demon, but I belive this routine is fairly fast and most important... it's generic and flexible. Regards, Daniel Berstein daber at pair.com
6. Re: Reverse() was: Win32Lib Update
- Posted by Robert Craig <rds at EMAIL.MSN.COM> Nov 28, 1998
- 422 views
Ad Rienks writes: > I'm sorry, but I made a mistake. The function reverse() *is* > in the 'official' release of Win32Lib v0.15a, it was only missing > from the copy sent with the calc021 program. Thanks for pointing this out. It was my mistake. It's corrected now. Since adding a reverse() function to misc.e for 2.1, I have to remove Cuny's reverse() before running win32lib programs. I accidentally uploaded calc021 minus his reverse(). This raises a couple of issues: 1. I should probably not make it an error (just a warning) to override a global symbol with a local symbol. The local should take precedence within the file it is declared in. I'm not sure if I'll do it for this release. It involves changes to compile-time symbol lookup, run-time symbol lookup (trace and routine_id) as well as the bind.ex program. It would alleviate some of the namespace conflicts. 2. Which reverse() is the fastest? I was planning to add a Euphoria-coded reverse() to misc.e. A few weeks ago I coded reverse5() below, but it looks like reverse2() (Hawke) is the fastest, so I'll use his unless someone comes up with something even faster. -- taken from Irv's last post: without type_check include machine.e tick_rate(100) sequence before, after atom start, fini before = "Now is the time for all good men to come get drunk at the party." function reverse1(sequence s) -- Ralf sequence r r = {} for i = 1 to length(s) do r = prepend(r,s[i]) end for return r end function function reverse2(sequence data) -- Hawke' (newer one) sequence result integer len len = length(data) result = repeat(0,len) --BOOM, call alloc *once* for toindex = 1 to len do -- initial value of len sets the limit result[toindex] = data[len] len = len - 1 end for return result end function function reverse3 (sequence s) -- Irv atom temp, left, right left = 1 right = length(s) while left < right do temp = s[left] s[left] = s[right] s[right] = temp left = left + 1 right = right - 1 end while return s end function function reverse4 (sequence s) -- Ad Rienks atom x sequence r x = length(s) r = repeat(0,x) for i = 1 to x do r[i] = s[x-i+1] end for return r end function function reverse5(sequence s) -- Rob Craig object temp integer n n = length(s)+1 for i = 1 to floor((n-1)/2) do temp = s[i] s[i] = s[n-i] s[n-i] = temp end for return s end function function reverse6( sequence s1 ) -- David Cuny -- reverse a sequence -- Ex: reverse( "12345" ) -- --> "54321" sequence s2 s2 = {} for i =length(s1) to 1 by -1 do s2 = append( s2, s1[i] ) end for return s2 end function procedure measure(sequence name) -- time a routine integer id id = routine_id(name) start = time() for i = 1 to 100000 do -- not a normal call, but shouldn't make much difference after = call_func(id, {before}) end for fini = time() printf(1, "%s: %.2f seconds for 100000 iterations\n", {name, fini-start}) puts(1, after) puts(1, '\n') end procedure measure("reverse1") -- 5.06 measure("reverse2") -- 3.30 measure("reverse3") -- 3.68 measure("reverse4") -- 4.08 measure("reverse5") -- 3.86 measure("reverse6") -- 5.20 Regards, Rob Craig Rapid Deployment Software http://members.aol.com/FilesEu/
7. Re: Reverse() was: Win32Lib Update
- Posted by Daniel Berstein <daber at PAIR.COM> Nov 28, 1998
- 448 views
- Last edited Nov 29, 1998
>I'm no speed demon, but I belive this routine is fairly fast and most >important... it's generic and flexible. Well.... after Rob's post I realized that it ain't "fairly fast"... ;) At least compared to the other 6 routines posted. But I still like the "idea" of: 1.- Iterate n/2 times 2.- Don't create a new sequence. What if the sequence is very large? Memory swaping time would be significant? Regards, Daniel Berstein daber at pair.com
8. Re: Reverse() was: Win32Lib Update
- Posted by Hawke <mdeland at NWINFO.NET> Nov 28, 1998
- 430 views
Daniel Berstein wrote: >But I still like the "idea" of: >1.- Iterate n/2 times that has promise... need better implementation that doesn't require any calculations *within* the loop (which is the other reason reverse#2 is the fastest: i only do a *single* "inc()" with the next best doing a subtraction AND an inc() within the loop, requiring TWICE as many clock ticks. >2.- Don't create a new sequence. >What if the sequence is very large? >Memory swaping time would be significant? actually, repeat() is extremely fast, likely nothing more than: function repeat(object what, integer howmuch) pointertype pntr, where pntr = alloc(howmuch + GLOBALVARSEQOVERHEAD) where= pntr + GLOBALVARSEQOVERHEAD memset(where, what, howmuch) --return pointer --return where --dunno which you return... end function so the very large sequence issue is not a factor. we can then address the memory swapping time by simply saying what was in the comments in my first post of reverse2(), namely: we are only swapping pointers. *fast* okay..... i thought of another way, that is 'approaching assembly' and, at this point, i'm rather sure this is bad code... it's presented as a *concept* or as *pseudocode* and if someone can actually take this and make it work, i'd be happy to share credit :) this may work real well for single dim sequences... ie: strings. it could be *the* speed demon for strings, i think... can't use memcopy/memset that i can see, as we cannot "reverse" the order of their element grabbing, so that's out. at this point, the only reason it "won't work" is that we aren't returning a *sequence* but a pointer... but then, what is the *actual* definition of a sequence after all... likely a *pointer* to a block of data, and that data is either a byte(s), or a pointer(s) to another block(s) of data at an element's index for atoms and other sequences occupying that element, along with a few bytes for overhead describing start and end memory addresses... so, how do i retrieve the overhead? if i had the overhead, we could, in theory, recreate a "sequence pointer" by prepend/appending the overhead to the pointer variable in the example below... if Rob is planning to use the #2 algorithm for reverse, i would think an examination of this methodology would be in order first. I'm not sure anyone but Rob, with his intimate knowledge of "sequence" as defined in ex(w).exe, could pull this off. Pete, of course, might, for PEU, be able to as well... and i'm not insulting anyone's intelligence with that last paragraph, nor am i intending to do so, nor am i intending to ruffle any feathers. please, don't take what i said wrong... i would really like to see someone make this algorithm work, at least for strings, to see it's benchmrk against the fastest algorithm to date. code follows. take care all--Hawké -----reverse function presented in Rob's Measure() format: -----Hawké, tweak to reverse2 -----begin pseudocode of non-functional function function reverse7( sequence data ) object old integer len atom pointer len = length(data) pointer = alloc(len) -- + GLOB_VAR_SEQ_OVERHEAD?? --if not alloc() then blahblahblah end if for toindex = 1 to len do old = peek( data + len, 1 ) -- +/- GLOB_VAR_SEQ_OVERHEAD?? poke( pointer + toindex, old ) len = len - 1 end for ----ummm what do we do about the return??? ----return pointer???? NOT! it's not a sequence... end function -----------end broken function
9. Re: Reverse() was: Win32Lib Update
- Posted by Robert Craig <rds at EMAIL.MSN.COM> Nov 29, 1998
- 410 views
I tweaked mine a bit to eliminate a subtraction. It now seems to be a tad faster than Hawke's, but they're close enough that I decided to try various lengths of sequence. function reverse5(sequence s) -- Rob Craig object temp integer n n = length(s) for i = 1 to floor(n/2) do temp = s[i] s[i] = s[n] s[n] = temp n = n - 1 end for return s end function length reverse2 (Hawke) reverse5 (Rob) 0 0.33 0.25 1 0.43 0.25 2 0.50 0.48 5 0.65 0.60 10 0.84 0.85 100 5.01 4.55 1000 62.33 48.19 10000 830.77 528.14 Regards, Rob Craig Rapid Deployment Software http://members.aol.com/FilesEu/
10. Re: Reverse() was: Win32Lib Update
- Posted by Albert Brauneis <Dajawu36 at AOL.COM> Nov 29, 1998
- 448 views
Rob, Can you test my reverse function out and compare its speed to yours and hawkey's? Thanks Albert
11. Re: Reverse() was: Win32Lib Update
- Posted by Robert Craig <rds at EMAIL.MSN.COM> Nov 29, 1998
- 458 views
Albert Brauneis writes: > Can you test my reverse function out and compare its speed to > yours and hawkey's? Your inner loop is: back = back & rev[junk] This is wrong. What if rev[junk] is a sequence? You should have said: back = append(back, rev[junk]) which is the way you originally had it. append() will be just as fast as &. Looping with append() will be similar to Cuny's reverse(), which is one of the slowest. Timing code is not rocket science. Just use: atom t t = time() for i = 1 to 10000 do -- call your routine here end for ? time() - t Regards, Rob Craig Rapid Deployment Software http://members.aol.com/FilesEu/
12. Re: Reverse() was: Win32Lib Update
- Posted by Daniel Berstein <daber at PAIR.COM> Nov 29, 1998
- 424 views
>>2.- Don't create a new sequence. >>What if the sequence is very large? >>Memory swaping time would be significant? >actually, repeat() is extremely fast, likely nothing more than: > >function repeat(object what, integer howmuch) >pointertype pntr, where > pntr = alloc(howmuch + GLOBALVARSEQOVERHEAD) > where= pntr + GLOBALVARSEQOVERHEAD > memset(where, what, howmuch) > --return pointer > --return where --dunno which you return... >end function > >so the very large sequence issue is not a factor. That's not the point. The point is that if the sequence is very large, we can get off physical memory. Disk read/write is far slower than RAM. In such a situation would it be faster to use a slower algorithm, but that doesn't create a new sequence? Regards, Daniel Berstein daber at pair.com
13. Re: Reverse() was: Win32Lib Update
- Posted by Daniel Berstein <daber at PAIR.COM> Nov 29, 1998
- 410 views
>I tweaked mine a bit to eliminate a subtraction. >It now seems to be a tad faster than Hawke's, but they're >close enough that I decided to try various lengths >of sequence. >length reverse2 (Hawke) reverse5 (Rob) >0 0.33 0.25 >1 0.43 0.25 >2 0.50 0.48 >5 0.65 0.60 >10 0.84 0.85 >100 5.01 4.55 >1000 62.33 48.19 >10000 830.77 528.14 Mmmm... my machine says other thing. I also created another reverse routine, it's between your's and Hawke'. I suppose it's slower than Hawke''s routine because substraction is slower than addtion (complement-2 computed, then addition?). Does having a hard typed constant as end value of a loop increase performance? function reverse9(sequence s) integer n, m, q, k sequence r n = length(s) m = floor(n/2) r = repeat(0,n) q = n+1 for i = m to n do k = q-i r[k] = s[i] r[i] = s[k] end for return r end function Using the benchmark posted earlier (64 charcters sequence with 100000 iterations): reverse2 reverse5 reverse9 (Hawke) (Rob) (Daniel) 1.21 sec. 1.69 sec. 1.39 sec. The fastest (read: unbeatable) reverse function will be one that iterates n/2 times, and do not make any substraccion inside the loop. My machine is a Celeron 300, with *no* cache... I guess that gives pure algorithmic results? I'm having fun with this thread! Can we expand it to a recursive version too... Regards, Daniel Berstein daber at pair.com
14. Re: Reverse() was: Win32Lib Update
- Posted by Ralf Nieuwenhuijsen <nieuwen at XS4ALL.NL> Nov 29, 1998
- 434 views
>This raises a couple of issues: > 1. I should probably not make it an error (just a warning) to override > a global symbol with a local symbol. The local should > take precedence within the file it is declared in. > I'm not sure if I'll do it for this release. It involves changes > to compile-time symbol lookup, run-time symbol lookup > (trace and routine_id) as well as the bind.ex program. > It would alleviate some of the namespace conflicts. Ive mentioned this before, a warning might be in place, but you should always be able to overwrite a global identifer with a local identifer. I only think you should see a warning when you overwrite a global identifer. > 2. Which reverse() is the fastest? I was planning to add a > Euphoria-coded reverse() to misc.e. A few weeks ago > I coded reverse5() below, but it looks like reverse2() (Hawke) > is the fastest, so I'll use his unless someone comes up > with something even faster. Good, it sounds like we're going to see some general purpose routines, and maybe containing a boolean type. Ive had many conflicts with them that I decided to add them to the beginning of every file *locally* .. if they would in an standard Euphoria file, one could trust the convention. Its just: global constant TRUE = 1, FALSE = 0, NONE = -1 global type boolean (object x) if integer (x) then return x > -2 and x < 2 else return FALSE end if end type The none is just a flag value. And could be used with result of find () or any of the input routines. Ralf
15. Re: Reverse() was: Win32Lib Update
- Posted by Ad Rienks <Ad_Rienks at COMPUSERVE.COM> Nov 29, 1998
- 436 views
Daniel wrote: >I'm having fun with this thread! Can we expand it to a recursive version= >too... >Regards, > Daniel Berstein So Ralf, it was a good idea of you (as many of your ideas are, btw) -- Slime, slime Ad