OpenG Coding Challenge - Remove Backspace
I really wonder who will win the contest... /Andreas
RE: OpenG Coding Challenge - Remove Backspace
I hav just returned from a week-long trip and will be moving forward with the judging. Regards, -Jim Kring -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Andreas Nilsson Sent: Tuesday, May 11, 2004 12:27 AM To: Info-Labview Mailing List (E-mail) Subject: OpenG Coding Challenge - Remove Backspace I really wonder who will win the contest... /Andreas
OpenG Coding Challenge - Remove Backspace
Hello Info-LV'ers, I have started a contest to create a high-performance VI that removes backspace characters (and the characters preceding them) from a string. The wining entry will become part of the OpenG Toolkit. (Note that VI Icons will be judged separately). Visit http://openg.org page for more info and download the example. Entries must be received by April 31st. http://www.openg.org/tiki/tiki-index.php?page=OpenG+Coding+Challenge+-+Remove+Backspace Regards, -Jim Kring
Re: OpenG Coding Challenge - Remove Backspace
Mike, Here is the problem description that I put up on the challenge page. This isn't an extremely hard challenge, but it is a fun problem. Also, you can spend additional effort trying to shave off the last few milliseconds. -Jim http://www.openg.org/tiki/tiki-index.php?page=OpenG+Coding+Challenge+-+Remove+Backspace Background When you are typing at a terminal (telnet for example) and you press the backspace key, a \b (0x08) character is sent via TCP-IP. The server that is parsing the text must interpret this string and remove the preceding character, which may have already been transmitted over the network. If the server receives a string like This is a test\b\b\b\bgood test for removing backspaces., it should remove the backspaces and the preceding characters so that the string becomes This is a good test for removing backspaces. Since there were four (4) backspaces we have to remove the backspaces and the four preceding characters t, e, s, and t. Easy, huh? But how do you do it quickly? Notice that the example shown above uses both a Build Array and Delete From Array in a loop. This is a performance no-no. It works but we can do a lot better. *Hint* - don't build/delete an array (or concatenate/split strings) in a loop. Ross, Michael wrote: I am curious, what makes this an intersting problem? What makes it hard? Also, what would be the application of this vi? These are not meant to be rhetorical questions, though they can certainly sound that way in an email. I have done just enough screwing around with strings to see that they are irritating, but I haven't had any intractable problem. In other words I am pretty ingnorant of the subject. Mike -Original Message- From: jkring [mailto:[EMAIL PROTECTED] Sent: Saturday, March 27, 2004 1:07 AM To: info-labview Subject: OpenG Coding Challenge - Remove Backspace Hello Info-LV'ers, I have started a contest to create a high-performance VI that removes backspace characters (and the characters preceding them) from a string. The wining entry will become part of the OpenG Toolkit. (Note that VI Icons will be judged separately). Visit http://openg.org page for more info and download the example. Entries must be received by April 31st. http://www.openg.org/tiki/tiki-index.php?page=OpenG+Coding+Challenge+-+Rem ove+B Backspace Regards, -Jim Kring
Re: OpenG Coding Challenge - Remove Backspace
Marco Tedaldi wrote: Jim Kring wrote: Hello Info-LV'ers, I have started a contest to create a high-performance VI that removes backspace characters (and the characters preceding them) from a string. The wining entry will become part of the OpenG Toolkit. (Note that VI Icons will be judged separately). http://www.openg.org/tiki/tiki-index.php?page=OpenG+Coding+Challenge+-+Remove+Backspace That's just depressing! There are people in the rankint with a speedup of about 160! And I've built two versions... one which completes in about halve the time and another one which takes longer than the original! :-( Are the Results on the site really true? I allmost can't believe it! But I'm trying :-) Bye Marco Hi Marco, Yes the results are real ;-) Also, all of the top entries are very similar to the example, but do not use build array or delete from array. Keep trying and good luck. Regards, -Jim
RE: OpenG Coding Challenge - Remove Backspace
Mike, Based on a lot of similar feedback, we have updated the Functional Requirements to the following (thanks to Christian Altenbach for his work on this): -- Removes all backspaces (Slash Code: \b, ASCII Hex: 0x08) and the characters preceding them. If there are N consecutive backspaces, N preceding characters will be removed. Extra backspaces are discarded whenever the edited string reaches zero length. This VI is useful for terminal programs that are processing user input received by TCP-IP. -- Hopefully this catches all of our limit conditions (empty string, all backspaces, no backspaces, etc). Yes, we will be testing for accuracy as well as performance. Regards, -Jim Ross, Michael wrote: Mine does spurious \b's so go for it! mike -Original Message- From: Scott Hannahs [mailto:[EMAIL PROTECTED] In terms of the problem description, must the VI handle the case where there are more \b (backspaces) than there are characters? If this is true then the VIs should pass an accuracy test as well as performance! -Scott
Re: OpenG Coding Challenge - Remove Backspace
Alex Le Dain wrote: I would also think that re-entrancy here is only for testing as near to optimum, presumably building a VI into an EXE would achive the same increase in performance as is achieved with reentrant=TRUE, as the UI and debug code are removed then. Is that correct Jim? We'll sure find out ;-) -Jim
Re: OpenG Coding Challenge - Remove Backspace
Craig Graham wrote: - Original Message - From: Marco Tedaldi [EMAIL PROTECTED] To: Info-LabVIEW [EMAIL PROTECTED] Sent: Monday, March 29, 2004 12:59 PM Subject: Re: OpenG Coding Challenge - Remove Backspace That's just depressing! There are people in the rankint with a speedup of about 160! And I've built two versions... one which completes in about halve the time and another one which takes longer than the original! :-( Are the Results on the site really true? I allmost can't believe it! But I'm trying :-) Well, my first attempt came in at a tad under 20ms. I'll have another crack soon; obviously not much point submitting at this stage. But I also am trying. :) For the short term, take the current performance rankings with a grain of salt. There are statistical uncertainties in those numbers and there are platform and LabVIEW version differences, as well. We are working on a test plan that will test the entries on a variety of platforms and under many input conditions. Ultimately we want to account for (and try to eliminate) any uncertainties. Regards, -Jim
Re: OpenG Coding Challenge - Remove Backspace
Craig Graham wrote: Hmm. Just got round to my second approach and it also takes 20ms. However if I change it to subroutine it comes down to 8ms here. Have the posted results been normal priority or subroutine? For the results currently posted, all entry VIs were set to the following: Execution System = Same as Caller Priority = Time Critical Priority Is Reentrant = TRUE -Jim
RE: OpenG Coding Challenge - Remove Backspace
It will be some work, but something like the evaluation done by NI on the different submissions. My vote is evaluation for not only minimum time but memory foot print etc. For the 1st NI challenge I was just out of the top 10, but I was about 0.1% of the size of any of the top 10. I always thought that should count for something. I think the fastest entries in this contest will also be very lean memorywise. This problem does not benefit from the lookup table techniques that worked so well in the NI challenge. next is average speed on multiple platforms. :-) (mine is still in the 20 mS range, but given that the peecee has a factor of 2 better compiler, and this is on an old 800 Mhz machine, it might come close to the posted times). It may be very interesting to create the executable and then profile it with some of the high end (not NI) performance tools. The best way to estimate your speed is to run both the example and your vi on your machine. Multiply the ratio of these by the speed of the example on the official machine (1008.6 ms). This should give you a decent prediction of your official time, despite the differences in hardware. It worked for me. My ratio here at home predicted my official time quite well. In fact, you may want to make a small change to your copy of Time Remove Backspace.vi to have it estimate the official time for you. Paul Brown
Re: OpenG Coding Challenge - Remove Backspace
Hmm. Just got round to my second approach and it also takes 20ms. However if I change it to subroutine it comes down to 8ms here. Have the posted results been normal priority or subroutine? -- Dr. Craig Graham, Software Engineer Advanced Analysis and Integration Limited, UK. http://www.aail.co.uk/
Re: OpenG Coding Challenge - Remove Backspace
Craig Graham wrote: Hmm. Just got round to my second approach and it also takes 20ms. However if I change it to subroutine it comes down to 8ms here. Have the posted results been normal priority or subroutine? Apparently the tests are being done reentrant, but not with the VIs set to subroutine. Both changes give the same doubling in performance- I assume from ditching debug and UI code internally. Does a similar speedup from ditching debug code occur naturally in a built app for VIs that are not reentrant? I've never noticed, but I've never bothered looking at the effects of things like this before. -- Dr. Craig Graham, Software Engineer Advanced Analysis and Integration Limited, UK. http://www.aail.co.uk/
Re: OpenG Coding Challenge - Remove Backspace
Craig Graham [EMAIL PROTECTED] wrote: Apparently the tests are being done reentrant, but not with the VIs set to subroutine. Both changes give the same doubling in performance- I assume from ditching debug and UI code internally. Does a similar speedup from ditching debug code occur naturally in a built app for VIs that are not reentrant? I've never noticed, but I've never bothered looking at the effects of things like this before. No, removing debugging only, will result in a gain of a few % execution speed at most. What speeds up things is, that for time critical or subroutine priority VIs, LabVIEW not only disables front panel updates (done anyway if the panel is not open), but even the code necessary to buffer the data for front panel display. A bitch to debug such a VI, (you really can't ;-) but a nice solution for a small atomic function, which has been throughly debugged beforehand. Don't do it for long executing functions though. LabVIEWs priority scheme is very strict and as long as a high priority clump (subVI) is executing in an execution system, little else will happen in that execution system, although in LabVIEW 7 this is a little aleviated through the default allocation of multiple OS threads per execution system. Rolf Kalbermatter CIT Engineering Nederland BVtel: +31 (070) 415 9190 Treubstraat 7H fax: +31 (070) 415 9191 2288 EG Rijswijkhttp://www.citengineering.com Netherlands mailto:[EMAIL PROTECTED]
Re: OpenG Coding Challenge - Remove Backspace
Rolf Kalbermatter wrote: What speeds up things is, that for time critical or subroutine priority VIs, LabVIEW not only disables front panel updates (done anyway if the panel is not open), but even the code necessary to buffer the data for front panel display. A bitch to debug such a VI, (you really can't ;-) but This can't be all there is to it though. Execution times (ms) for consecutive tests of a sub-VI; 29.6, 29.3Normal priority, not reentrant, panel open. 25.9, 26.4Normal priority, not reentrant, panel closed. 9.6, 9.6Normal priority, reentrant, panel closed. Going from non-reentrant to reentrant more than doubles the performance. Simply closing the panel to disable GUI code gives a comparitively slight improvement. Note that all VIs were saved to disk before running the tests. Is the data copied to the front panel even if the front panel is not open, and the update code to copy from the buffers to the screen is the only thing disabled when a VI is closed? It does not seem likely, since if you open a subVI after it has executed, the front panel does not contain the data loaded in to it during execution. -- Dr. Craig Graham, Software Engineer Advanced Analysis and Integration Limited, UK. http://www.aail.co.uk/
RE: OpenG Coding Challenge - Remove Backspace
Craig Graham [mailto:[EMAIL PROTECTED] wrote: Rolf Kalbermatter wrote: What speeds up things is, that for time critical or subroutine priority VIs, LabVIEW not only disables front panel updates (done anyway if the panel is not open), but even the code necessary to buffer the data for front panel display. A bitch to debug such a VI, (you really can't ;-) but This can't be all there is to it though. Execution times (ms) for consecutive tests of a sub-VI; 29.6, 29.3Normal priority, not reentrant, panel open. 25.9, 26.4Normal priority, not reentrant, panel closed. 9.6, 9.6Normal priority, reentrant, panel closed. Going from non-reentrant to reentrant more than doubles the performance. Simply closing the panel to disable GUI code gives a comparitively slight improvement. Note that all VIs were saved to disk before running the tests. An important remark, a otherwise your timings will be rather off. Is the data copied to the front panel even if the front panel is not open, and the update code to copy from the buffers to the screen is the only thing disabled when a VI is closed? It does not seem likely, since if you open a subVI after it has executed, the front panel does not contain the data loaded in to it during execution. Well that is indeed an indication that it is not copying data on closed front panels but I'm not entirely sure. Removing debugging only however will result in even less performance increase. So it can't be about debugging at all. It maybe has to do about the dataspace preparation then. For non reetrant VIs the data space is shared among all instances and probably needs to be initialized somehow each time the VI is called. Reentrant VIs maintain each their own dataspace and need no additional initialization before each call. Just a guess really! Rolf Kalbermatter CIT Engineering Nederland BVtel: +31 (070) 415 9190 Treubstraat 7H fax: +31 (070) 415 9191 2288 EG Rijswijkhttp://www.citengineering.com Netherlands mailto:[EMAIL PROTECTED]
RE: OpenG Coding Challenge - Remove Backspace
Paul Brown wrote: The best way to estimate your speed is to run both the example and your vi on your machine. Multiply the ratio of these by the speed of the example on the official machine (1008.6 ms). This should give you a decent prediction of your official time, despite the differences in hardware. It ain't necessarily so. [Be thankful you can't hear my singing!] My entry is 10% slower under LV7 and OS X than under LV6 and OS 9, but the original example slows down 2.5X with the same change in environment. Not all types of code scale the same. -- EnWirementally, Paul F. Sullivan SULLutions (781)769-6869 when a single discipline is not enough visit http://www.SULLutions.com
Re: OpenG Coding Challenge - Remove Backspace
On Wed, 31 Mar 2004 23:01:06 +0100, Craig Graham [EMAIL PROTECTED] wrote: Apparently the tests are being done reentrant, but not with the VIs set to subroutine. Both changes give the same doubling in performance- I assume from ditching debug and UI code internally. Does a similar speedup from ditching debug code occur naturally in a built app for VIs that are not reentrant? I've never noticed, but I've never bothered looking at the effects of things like this before. Just be careful. The penalty of reentrancy is memory. Marking all your VI's reentrant might give some increased processing speed but as each instance of the VI has it's own memory space, so depending on what you're doing making all your VI's reentrant can cripple you with memory requirements (especially with low RAM systems like FP controllers). I would also think that re-entrancy here is only for testing as near to optimum, presumably building a VI into an EXE would achive the same increase in performance as is achieved with reentrant=TRUE, as the UI and debug code are removed then. Is that correct Jim? cheers, Alex.
Re: OpenG Coding Challenge - Remove Backspace
Alex Le Dain [EMAIL PROTECTED] wrote: Just be careful. The penalty of reentrancy is memory. Marking all your VI's reentrant might give some increased processing speed but as each instance of the VI has it's own memory space, so depending on what you're doing making all your VI's reentrant can cripple you with memory requirements (especially with low RAM systems like FP controllers). I would also think that re-entrancy here is only for testing as near to optimum, presumably building a VI into an EXE would achive the same increase in performance as is achieved with reentrant=TRUE, as the UI and debug code are removed then. Is that correct Jim? No I don't think so. Unless NI made some significant changes in LabVIEW 7.0. building an application is just about the same performance gain as disabling the debugging flag. I have older figures but this resulted in LabVIEW 5 and 6 in gains of a few % and is therefore bound to get almost lost in the noise of the measurement accuracy. Rolf Kalbermatter CIT Engineering Nederland BVtel: +31 (070) 415 9190 Treubstraat 7H fax: +31 (070) 415 9191 2288 EG Rijswijkhttp://www.citengineering.com Netherlands mailto:[EMAIL PROTECTED]
RE: OpenG Coding Challenge - Remove Backspace
Jim, Are you going to post new times? April 30th deadline is approaching fast and if you leave it too close to the dead line some of us may not have a chance to re submit new/improved entries. -Sam -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Jim Kring Sent: Friday, April 02, 2004 11:33 AM To: Alex Le Dain Cc: [EMAIL PROTECTED]; InfoLabVIEW Subject: Re: OpenG Coding Challenge - Remove Backspace Alex Le Dain wrote: I would also think that re-entrancy here is only for testing as near to optimum, presumably building a VI into an EXE would achive the same increase in performance as is achieved with reentrant=TRUE, as the UI and debug code are removed then. Is that correct Jim? We'll sure find out ;-) -Jim
Re: OpenG Coding Challenge - Remove Backspace
Alex Le Dain wrote: Oh dear, the list appears to have died again. Just be careful. The penalty of reentrancy is memory. Marking all your VI's reentrant might give some increased processing speed but as each instance of the VI has it's own memory space, so depending on what you're doing making all your VI's reentrant can cripple you with memory requirements (especially with low RAM systems like FP controllers). It depends on what you're doing. If you are using the VI in multiple places, the question of whether or not to make it re-entrant is probably dominated by functional requirements- especially if there are uninitialised shift registers storing state information. If you have a sub VI called at only one point in the code, then there doesn't seem to be any loss to making it reentrant; you still only have one copy and you get the speed boost. I would also think that re-entrancy here is only for testing as near to optimum, presumably building a VI into an EXE would achive the same increase in performance as is achieved with reentrant=TRUE, as the UI and debug code are removed then. Is that correct Jim? Yes. I've never noticed the speed increase in a built app, but if remove panel is allowed to default to true for the subVI then it runs about as fast when built as if it's made reentrant and run in the development environment. -- Dr. Craig Graham, Software Engineer Advanced Analysis and Integration Limited, UK. http://www.aail.co.uk/
Re: OpenG Coding Challenge - Remove Backspace
Sam Behashtei wrote: Jim, Are you going to post new times? April 30th deadline is approaching fast and if you leave it too close to the dead line some of us may not have a chance to re submit new/improved entries. -Sam What kind of message does that give? You're already best so can't be arsed improving? :) -- Dr. Craig Graham, Software Engineer Advanced Analysis and Integration Limited, UK. http://www.aail.co.uk/
Re: OpenG Coding Challenge - Remove Backspace
Jim Kring wrote: Hello Info-LV'ers, I have started a contest to create a high-performance VI that removes backspace characters (and the characters preceding them) from a string. The wining entry will become part of the OpenG Toolkit. (Note that VI Icons will be judged separately). http://www.openg.org/tiki/tiki-index.php?page=OpenG+Coding+Challenge+-+Remove+Backspace That's just depressing! There are people in the rankint with a speedup of about 160! And I've built two versions... one which completes in about halve the time and another one which takes longer than the original! :-( Are the Results on the site really true? I allmost can't believe it! But I'm trying :-) Bye Marco
Re: OpenG Coding Challenge - Remove Backspace
Are the Results on the site really true? I allmost can't believe it! But I'm trying :-) They are probably quite true. My best vi so far does it 75 times faster than the example. Like Jim said, you will need to stop resizing arrays in order to get the best performance. Paul Brown
Re: OpenG Coding Challenge - Remove Backspace
- Original Message - From: Marco Tedaldi [EMAIL PROTECTED] To: Info-LabVIEW [EMAIL PROTECTED] Sent: Monday, March 29, 2004 12:59 PM Subject: Re: OpenG Coding Challenge - Remove Backspace That's just depressing! There are people in the rankint with a speedup of about 160! And I've built two versions... one which completes in about halve the time and another one which takes longer than the original! :-( Are the Results on the site really true? I allmost can't believe it! But I'm trying :-) Well, my first attempt came in at a tad under 20ms. I'll have another crack soon; obviously not much point submitting at this stage. But I also am trying. :) -- Dr. Craig Graham, Software Engineer Advanced Analysis and Integration Limited, UK. http://www.aail.co.uk/
Re: OpenG Coding Challenge - Remove Backspace
Quoting Marco Tedaldi [EMAIL PROTECTED]: I tried to build somethin cempletely different (much more complicated). Marco, The solution is not always in complexity. Look at the VI memory usage (from VI properties): Slow Sample VI: Code: 3.0K, data: 1.2K My current solution is significantly leaner: My VI: Code 1.3K, data: 0.9K Simplicity is the key! :-) Cheers Christian
RE: OpenG Coding Challenge - Remove Backspace
Mine does spurious \b's so go for it! mike -Original Message- From: Scott Hannahs [mailto:[EMAIL PROTECTED] In terms of the problem description, must the VI handle the case where there are more \b (backspaces) than there are characters? If this is true then the VIs should pass an accuracy test as well as performance! -Scott
RE: OpenG Coding Challenge - Remove Backspace
I think I have those covered. I don't know enough to shorten my time anymore. I look forward to seeing the other VIs. I have no ideas how to make it any cleaner. Mike -Original Message- From: jkring [mailto:[EMAIL PROTECTED] Sent: Tuesday, March 30, 2004 7:24 PM To: Ross, Michael Cc: Scott Hannahs; info-labview Subject: RE: OpenG Coding Challenge - Remove Backspace Mike, Based on a lot of similar feedback, we have updated the Functional Requirements to the following (thanks to Christian Altenbach for his work on this): -- Removes all backspaces (Slash Code: \b, ASCII Hex: 0x08) and the characters preceding them. If there are N consecutive backspaces, N preceding characters will be removed. Extra backspaces are discarded whenever the edited string reaches zero length. This VI is useful for terminal programs that are processing user input received by TCP-IP. -- Hopefully this catches all of our limit conditions (empty string, all backspaces, no backspaces, etc). Yes, we will be testing for accuracy as well as performance. Regards, -Jim Ross, Michael wrote: Mine does spurious \b's so go for it! mike -Original Message- From: Scott Hannahs [mailto:[EMAIL PROTECTED] In terms of the problem description, must the VI handle the case where there are more \b (backspaces) than there are characters? If this is true then the VIs should pass an accuracy test as well as performance! -Scott
RE: OpenG Coding Challenge - Remove Backspace
I think I have those covered. I don't know enough to shorten my time anymore. I look forward to seeing the other VIs. I have no ideas how to make it any cleaner. It will be some work, but something like the evaluation done by NI on the different submissions. My vote is evaluation for not only minimum time but memory foot print etc. For the 1st NI challenge I was just out of the top 10, but I was about 0.1% of the size of any of the top 10. I always thought that should count for something. next is average speed on multiple platforms. :-) (mine is still in the 20 mS range, but given that the peecee has a factor of 2 better compiler, and this is on an old 800 Mhz machine, it might come close to the posted times). It may be very interesting to create the executable and then profile it with some of the high end (not NI) performance tools. -Scott
