Computer Science Canada DWITE io allotted time

Author:  ttm [ Fri Dec 02, 2011 11:13 pm ]
Post subject:  DWITE io allotted time

Completely not important, but on the DWITE, the language io is allotted 2500 ms while turing is allotted 6000, but in practice, io is 15x slower than turing.

The following io code takes 12,105 ms to run on my computer
 code: fib := method (i, if (i <= 1, 1, fib (i - 1) + fib (i - 2))) d := Date now asNumber fib (30) ((Date now asNumber - d) * 1000) println

whereas the following turing code takes only 790 ms
 code: fcn fib (i : int) : int     if i <= 1 then         result 1     else         result fib (i - 1) + fib (i - 2)     end if end fib var d : int := Time.Elapsed var n : int := fib (30) put Time.Elapsed - d

I know this isn't really a rigorous test, but for most programming problems, function calling and math are pretty essential. Update/fix/change?

 Author: ttm [ Fri Dec 02, 2011 11:15 pm ] Post subject: Re: DWITE io allotted time Also latest binaries are here http://iobin.suspended-chord.info/.

Author:  chrisbrown [ Sat Dec 03, 2011 12:39 am ]
Post subject:  Re: DWITE io allotted time

Your test actually shows why time restrictions exist. Turing got lucky on this one, but in general, an exponential-runtime function like that should perform very poorly.

Those fib functions have an O(2^n) runtime, where n is the argument to fib. The big-Oh notation means runtime is given by 2^n * C, where C is some unknown constant. All your test shows is that the C for your io function is about 15 times larger than the C for your Turing one. Regardless, neither would be acceptable for calculating fib(1000).

Time restrictions exist to filter out slow programs, not slow languages.
 io: fib := method(n,     f1 := 0     f2 := 1     t := 0     n repeat(         t = f2         f2 = f1 + f2         f1 = t)     f1) fib(1000) println

 Author: Dan [ Sat Dec 03, 2011 3:50 am ] Post subject: RE:DWITE io allotted time If you want a fair test with turing you also have to factor in the time turing takes to start the IDE, open the file and then run it. The reason why turing has a higher time limit is the convoluted ways we have to run it.

 Author: Insectoid [ Sat Dec 03, 2011 9:10 am ] Post subject: RE:DWITE io allotted time To be fair, there is a much, much faster implementation of the fib sequence using the closed-form equation. If you used that, you would not run into trouble. All languages are not equal. Some are better at some things, and others are better at others. Evidently your language was not optimal for your implementation.

 Author: mirhagk [ Sat Dec 03, 2011 9:55 am ] Post subject: Re: RE:DWITE io allotted time Dan @ Sat Dec 03, 2011 3:50 am wrote:If you want a fair test with turing you also have to factor in the time turing takes to start the IDE, open the file and then run it. The reason why turing has a higher time limit is the convoluted ways we have to run it. Is OpenTuring going to be used in DWITE (meaning you could alter the code so you can actually compile from the command line)?

 Author: Insectoid [ Sat Dec 03, 2011 11:02 am ] Post subject: RE:DWITE io allotted time Once OpenTuring makes significant progress towards being worth using, it might be worth adding support for. But everyone that uses Turing, still uses Turing, and if we're going to include it in a contest, we'd better be using the same compiler they wrote their code for. OpenTuring needs to be marketed to teachers before it can gain any following. Replace out-of-date Turing with an improved, supported version in schools and it will see massive popularity. Since DWITE is a high-school contest, it makes sense to support the languages the schools' are teaching.

 Author: mirhagk [ Sat Dec 03, 2011 12:35 pm ] Post subject: RE:DWITE io allotted time I thought the current version of OpenTuring was the same compiler....

 Author: Dan [ Sat Dec 03, 2011 1:22 pm ] Post subject: Re: DWITE io allotted time OpenTuring has been added to DWITE since last round but it is not a replacement for Turing and has several issues. No one has made a proper run from command line for it. The current "-run" feature is basically a hack that has issues with the judge. The is no real release management or versioning for the project. Simply using git is not enough. The main branch is bascily being used as a devlopment branch. No unit testing is being done. No code review or qauility esurance steps are being preformed. There is no or litte documenation of new features (or even the features of Turing 4.1.2). The direction of OpenTuring is still unclear. No real (or active) bug tracker. This is not to say that the OpenTuring project is bad or doomed, it is just still very young and has many issues to work out. I would say it is immature to claim it is ready to be a replacment for Turing. Edit: mirhagk @ 3rd December 2011, 12:35 pm wrote:I thought the current version of OpenTuring was the same compiler.... The code started at Turing 4.1.2 a version of turing that was not pubicly released and should still be considered a beta. Since then serveral mostly untested changes to the language and IDE have been made.

 Author: mirhagk [ Sat Dec 03, 2011 2:44 pm ] Post subject: RE:DWITE io allotted time Okay, so do you suggest that it's not even ready to be used in schools?

 Author: Tony [ Sat Dec 03, 2011 2:55 pm ] Post subject: Re: RE:DWITE io allotted time If some particular school wants to live on the edge and run the daily build -- sure, it could be used. Though currently OpenTuring doesn't enjoy the discipline of not pushing faulty commits, and... http://en.wikipedia.org/wiki/Daily_build wrote:The critical piece of this process is to include new and revised tests as the project progresses. doesn't actually release any new tests.

 Author: ttm [ Sat Dec 03, 2011 3:14 pm ] Post subject: Re: DWITE io allotted time Hi; First, the ugly fib funciton was designed to have an exponential run time. There exists a constant time fibbonacci algorithm, but it's not really interesting to compare a 0.0001ms run time with a 0.0001ms run time. Next, the current version of OT is indeed just the original 4.1.12 relabeled, recompiled with optimisation enabled, and some minor other things. Its documentation is basically the same and needs serious updating. Anyone wanting to help out on that is welcome, get GitHub and HTML Help Workshop (http://www.microsoft.com/download/en/details.aspx?id=21138). There's lots of bugs in the current documentation, like broken links, stuff that isn't relevant anymore, etc. Next, I'm with Dan. I personally don't think schools should be starting to use OT just yet, because lacking a lot of finesse. I'm still in the process of getting the hang of Git and open source software development, and we've yet to set up a lot of things. The first OT release just a rush to get the code out to the world, I think. Ask Tristan. Last, original topic. Ok, maybe it's fair that Turing gets extra time because of its launch problems. What about the other languages? It's still unfair that io gets the same amount of time as C++, or Java. For example, on the DWITE round 1 question 4, C++ can easily brute-force the solution and run in the time range, whereas io can't possibly brute force it. Yes, brute forcing is a bad idea, but at least punish the faster languages for brute forcing. It's the algorithm that counts, not the language's speed.

 Author: Dan [ Sat Dec 03, 2011 4:10 pm ] Post subject: Re: DWITE io allotted time ttm @ 3rd December 2011, 3:14 pm wrote: Next, the current version of OT is indeed just the original 4.1.12 relabeled, recompiled with optimisation enabled, and some minor other things. Its documentation is basically the same and needs serious updating. Anyone wanting to help out on that is welcome, get GitHub and HTML Help Workshop (http://www.microsoft.com/download/en/details.aspx?id=21138). There's lots of bugs in the current documentation, like broken links, stuff that isn't relevant anymore, etc. I would be willing to spend some of my free time (the litte i have) helping out but am a bit reluctant to put time into OT intill some effort is put into organizing the project. Their does not seem to be any clear goal or direction for the project and I am very much against making changes to the language at a whim (i.e. throwing in hashmaps and OpenGL). As i told Tristan, CompSci.ca is willing to provide hosting services as well as other resources for the project. If you wish we could setup a mailing list or sub forum for OT discussion. ttm @ 3rd December 2011, 3:14 pm wrote: Last, original topic. Ok, maybe it's fair that Turing gets extra time because of its launch problems. What about the other languages? It's still unfair that io gets the same amount of time as C++, or Java. For example, on the DWITE round 1 question 4, C++ can easily brute-force the solution and run in the time range, whereas io can't possibly brute force it. Yes, brute forcing is a bad idea, but at least punish the faster languages for brute forcing. It's the algorithm that counts, not the language's speed. It would be very hard to balance this and the contestants are free to use any language for all or some subset of the questions. The reason Turing gets a time bonus was that the old launcher it's self took longer then 2.5 seconds in some odd cases (as we have a new launcher script I will proably be reevaluating the time Turing is given in the near future).

 Author: trishume [ Sat Dec 03, 2011 4:41 pm ] Post subject: Re: DWITE io allotted time Dan @ Sat Dec 03, 2011 1:22 pm wrote:OpenTuring has been added to DWITE since last round but it is not a replacement for Turing and has several issues. No one has made a proper run from command line for it. The current "-run" feature is basically a hack that has issues with the judge. The is no real release management or versioning for the project. Simply using git is not enough. The main branch is bascily being used as a devlopment branch. No unit testing is being done. No code review or qauility esurance steps are being preformed. There is no or litte documenation of new features (or even the features of Turing 4.1.2). The direction of OpenTuring is still unclear. No real (or active) bug tracker. This is not to say that the OpenTuring project is bad or doomed, it is just still very young and has many issues to work out. I would say it is immature to claim it is ready to be a replacment for Turing. Edit: mirhagk @ 3rd December 2011, 12:35 pm wrote:I thought the current version of OpenTuring was the same compiler.... The code started at Turing 4.1.2 a version of turing that was not pubicly released and should still be considered a beta. Since then serveral mostly untested changes to the language and IDE have been made. The beginnings of a FAQ: The general theme: No one has free time to help out so things that should happen don't. But it is not that bad. 1. What problem does it have with the judge? I know it is a hack. The interpreter is deeply integrated with the editor, so real command line would be difficult. 2. Versioning is coming once I merge the current development. I just need someone to test the current dev branch, as I have not compiled it and do not want to boot up my VM and test it. If some native windows person (ttm?) compiles and tests it I can merge the dev branch and tag it v1.0.0. Then I will start versioning. 3. We do use a dev branch. Look at the github network. The current package.zip is the packaged release (often more stable than master.) 4. I also have little free time. No one has time, or will possibly ever have time to write the thousands of required unit tests. Even the current Turing 4.1.1 is not unit tested. 5. Right. Only basic looking at all changes and running a limited test suite. But then again, no big changes that could cause huge problems have been made. 6. Yup. No one (myself included) wants to write documentation. 7. Basic plan: current -> new editor in Qt -> JIT compiler in LLVM -> cross-platform std lib -> fully cross-platform and compilable to executable. 8. Github issues. I check them and fix anything pressing.

 Author: mirhagk [ Sat Dec 03, 2011 5:08 pm ] Post subject: RE:DWITE io allotted time @Dan we should set up a sub-forum related purely to OpenTuring, and we should also provide the package to students in the Turing section (label as beta until it's fully tested of course)

 Author: Tony [ Sat Dec 03, 2011 5:18 pm ] Post subject: RE:DWITE io allotted time 2. doesn't make much sense to grab an arbitrary point in dev and call it v1.0.0. Is it stable and tested and feature complete? 3. if dev is more stable than master, you are doing it backwards. 4. doesn't matter. Test new code. I know that it's fun to hack on new features, and ignore testing, documentation, bug fixes, all of this "software project maintenance" stuff... but it's required for the project to be taken seriously.

 Author: crossley7 [ Sat Dec 03, 2011 8:46 pm ] Post subject: RE:DWITE io allotted time I'm fairly busy right now, but if I find at some point that I have a large amount of free time, I could start helping with some documentation (don't trust myself to help develop too much fresh code without any proper learning for efficient algorithms). However, this could be months down the road and I would test out those features at the same time as writing the documentation for them. But then again, this would be only if you feel comfortable with a high school student helping out with the project.

 Author: Tony [ Sat Dec 03, 2011 8:56 pm ] Post subject: Re: RE:DWITE io allotted time crossley7 @ Sat Dec 03, 2011 8:46 pm wrote:don't trust myself to help develop too much fresh code without any proper learning for efficient algorithms ideally a project maintainer would review and comment on changes before granting a pull request.

 Author: crossley7 [ Sat Dec 03, 2011 8:59 pm ] Post subject: RE:DWITE io allotted time Even if they would, my code is incredibly ugly and can be a nightmare to read. (if you have seen my dwite solutions you would know) I wouldn't want to force anyone to try to read it at this point. I'm trying to improve it but will go with my compsci class in school to do that.

 Author: ttm [ Sat Dec 03, 2011 10:33 pm ] Post subject: Re: DWITE io allotted time A few things. -Hi crossley7, we'd love to have you help; we're still in high school too. -I don't think anyone's being too negative. The project is kinda at a sucky baby state right now. -Another issue, our current planning system relies heavily on that evil tool called Facebook Chat >.< -Having compsci.ca host a project page would be much appreciated, but we don't have a website yet -We can make do with git's built-in bug tracker for now. -I'll get started fixing up the documentation soon (this weekend busy as hell seems like the world is due Monday) -How do you propose we get started with unit testing? -Your guidance is appreciated.

 Author: Tony [ Sat Dec 03, 2011 11:15 pm ] Post subject: Re: DWITE io allotted time ttm @ Sat Dec 03, 2011 10:33 pm wrote: -Having compsci.ca host a project page would be much appreciated, but we don't have a website yet what kind of a website are you thinking of ttm @ Sat Dec 03, 2011 10:33 pm wrote: -How do you propose we get started with unit testing? research your options and find a decent unit testing framework that will be compatible with this project.

 Author: trishume [ Sun Dec 04, 2011 9:26 am ] Post subject: Re: DWITE io allotted time What I meant by minor changes was no changes that are good targets for unit testing. OpenGL is a library interface with no computation. I have actually done testing (not huge industry-level testing but some) I have test suite files for both hash maps and OpenGL that I used to find bugs. I am now fairly confident in those features. For language testing I run my Turing in turing interpreter, which uses almost all turing language features (OO,exceptions,casting,pointers, etc...) Thus I am fairly confident in those features. The master as dev thing was when I was learning github and developing on my own machine. That stopped as soon as I pushed to github. And the dev branch is always less stable than master. Also, that time was the first time I had committed uncompiled code? Why? Ttm had made those changes and tested them but totally f'd up the git repo in his learning process. So I rolled back his changes and redid the good changes myself. I just needed them compiled to test for typos in the 10 characters I changed. The oops was me forgetting to add one of the changes ttm made. I'm tagging this version 1.0 because: - It is fairly stable and tested (80+ people and the only bug found is your -run one.) I know this isn't as good as unit testing, but it is pretty good. - I have to make something 1.0 or else not have version numbers. Which people seem to want.

 Author: ttm [ Sun Dec 04, 2011 2:22 pm ] Post subject: Re: DWITE io allotted time Ah-hem. -What about the 9000+ places where it says Turing when it should say OpenTuring -What about the bug where if you copy OpenTuring to another folder the splash and icons revert -The editor crash bug still happens if you're holding down a letter and double click -Structure complete doesn't completing functions marked as pervasive or body -Lack of documentation of new features, etc etc. -New features don't have syntax highlighting -The drawpic function doesn't actually work -etc Not that these are going to be solved immediately, but there's more than 1 bug. Anyways. I think 1.0 should have been just the exact original 4.1.12 with only a splash and name change, with hashmaps and whatever in 1.1, but seeing as 1.0 has already been done, there's not much we can do about that. Quote: what kind of a website are you thinking of Like this maybe? Will need additional planning. Quote: research your options and find a decent unit testing framework that will be compatible with this project. Doesn't really help but ok. VS has built-in unit testing features that may work.

 Author: Tony [ Sun Dec 04, 2011 2:40 pm ] Post subject: RE:DWITE io allotted time bugtracker -- github's or otherwise. It's unreasonable to keep track of bugs in forum posts. versioning -- could very well start at v0.1.x. If, for whatever reason, it must be 1.x, then maybe 1.0.0_RC1 ? Website -- Project Pages at github http://pages.github.com/ is likely your best bet. That could even be hooked up with a custom domain. I'm not going to tell you what specific testing framework to use, just nudge you in the right direction. Open this up as an issue, propose choices, invite discussion. This might seem mundane at the surface, but it will (well, should) become an integral part of the project. This is absolutely amazing -- http://www.sqlite.org/testing.html Quote: By comparison, the project has 1177 times as much test code and test scripts Quote: extensive testing also plays a vital role in maintaining and improving the quality of SQLite. This document has summarized the testing procedures that every release of SQLite undergoes with the hopes of inspiring the reader to understand that SQLite is suitable for use in mission-critical applications. Sure, OpenTuring might not have a goal of "production use". Fine. But you'd have a much easier time convincing people (teachers, school boards?) to switch from Turing, if you can show a reasonable level of stability. (A solid test suite also makes it incredibly easier to develop new features in the long run. This is from years of industry experience.)

 Author: trishume [ Sun Dec 04, 2011 4:19 pm ] Post subject: Re: DWITE io allotted time ttm @ Sun Dec 04, 2011 2:22 pm wrote:Ah-hem. -What about the 9000+ places where it says Turing when it should say OpenTuring -What about the bug where if you copy OpenTuring to another folder the splash and icons revert -The editor crash bug still happens if you're holding down a letter and double click -Structure complete doesn't completing functions marked as pervasive or body -Lack of documentation of new features, etc etc. -New features don't have syntax highlighting -The drawpic function doesn't actually work -etc Not that these are going to be solved immediately, but there's more than 1 bug. Anyways. I think 1.0 should have been just the exact original 4.1.12 with only a splash and name change, with hashmaps and whatever in 1.1, but seeing as 1.0 has already been done, there's not much we can do about that. Quote: what kind of a website are you thinking of Like this maybe? Will need additional planning. Quote: research your options and find a decent unit testing framework that will be compatible with this project. Doesn't really help but ok. VS has built-in unit testing features that may work. Github bug tracker!! Put them up!

 Author: trishume [ Sun Dec 04, 2011 4:31 pm ] Post subject: Re: RE:DWITE io allotted time Tony @ Sun Dec 04, 2011 2:40 pm wrote:bugtracker -- github's or otherwise. It's unreasonable to keep track of bugs in forum posts. versioning -- could very well start at v0.1.x. If, for whatever reason, it must be 1.x, then maybe 1.0.0_RC1 ? Website -- Project Pages at github http://pages.github.com/ is likely your best bet. That could even be hooked up with a custom domain. I'm not going to tell you what specific testing framework to use, just nudge you in the right direction. Open this up as an issue, propose choices, invite discussion. This might seem mundane at the surface, but it will (well, should) become an integral part of the project. This is absolutely amazing -- http://www.sqlite.org/testing.html Quote: By comparison, the project has 1177 times as much test code and test scripts Quote: extensive testing also plays a vital role in maintaining and improving the quality of SQLite. This document has summarized the testing procedures that every release of SQLite undergoes with the hopes of inspiring the reader to understand that SQLite is suitable for use in mission-critical applications. Sure, OpenTuring might not have a goal of "production use". Fine. But you'd have a much easier time convincing people (teachers, school boards?) to switch from Turing, if you can show a reasonable level of stability. (A solid test suite also makes it incredibly easier to develop new features in the long run. This is from years of industry experience.) I know of the benefits of unit testing and am a firm believer in them. I am writing unit tests for the new editor and my compiler. From now on any new features I write I will write tests for. Unfortunately, unit tests are only effective if they have reasonable code coverage. It would be damn near impossible for the meagre amount of unit tests we could write even if we had time to properly check all of the Turing interpreter. Also, it isn't easy to test code you didn't write. You end up looking at the code and thinking, "This is what it's meant to do" and coding buggy behaviour into the tests. Yes, you can figure out proper behaviour but this is hard in large confusing code bases. Even an efficient 11:1 code-test ratio would take 2+ million lines of code.

 Author: Tony [ Sun Dec 04, 2011 4:42 pm ] Post subject: Re: RE:DWITE io allotted time trishume @ Sun Dec 04, 2011 4:31 pm wrote:Unfortunately, unit tests are only effective if they have reasonable code coverage. You would be right, if we were talking about regression testing only. Edit: you are right that unit testing the existing code base comes with too high of a benefit per effort ratio. It could be covered with functional tests though. I think you've mentioned feeding a complicated source file to see if it compiles, which is basically the idea. Perhaps a more fine grained suite of functional tests, with validated outputs, could be put together with reasonable amount of effort.

 Author: Dan [ Sun Dec 04, 2011 5:09 pm ] Post subject: Re: DWITE io allotted time trishume @ 4th December 2011, 4:19 pm wrote: Github bug tracker!! Put them up! Better then nothing, but personaly i think you should try to keep the barrier to users reporting bugs as small as possible. Requireing them to sing up for a GitHub account may deter people from reporting bugs. I think the best method might be setting up public mailing lists for devloper discussion and one for user support/bug reporting (which devlopers could then create issues for). Another current issue is your licensing. Right now you have GPL, confidential and copyrighted code in the repo with the OpenTuring code. As it stands you could proably be sued or get a DMCA take down from sun microsystems, microsoft, and others. You also have a copy of the SciFi novel writer, Michelle Sagara's home page in there which is really crazy.

 Author: Tony [ Sun Dec 04, 2011 5:32 pm ] Post subject: Re: DWITE io allotted time sun microsystems Oracle.

 Author: ProgrammingFun [ Sun Dec 04, 2011 5:43 pm ] Post subject: Re: DWITE io allotted time Tony @ Sun Dec 04, 2011 5:32 pm wrote: sun microsystems Oracle. I pointed that out when UTSC recently said that their coop partners include Sun Microsystems

 Author: trishume [ Sun Dec 04, 2011 6:38 pm ] Post subject: Re: DWITE io allotted time Dan @ Sun Dec 04, 2011 5:09 pm wrote:trishume @ 4th December 2011, 4:19 pm wrote: Github bug tracker!! Put them up! Better then nothing, but personaly i think you should try to keep the barrier to users reporting bugs as small as possible. Requireing them to sing up for a GitHub account may deter people from reporting bugs. I think the best method might be setting up public mailing lists for devloper discussion and one for user support/bug reporting (which devlopers could then create issues for). Another current issue is your licensing. Right now you have GPL, confidential and copyrighted code in the repo with the OpenTuring code. As it stands you could proably be sued or get a DMCA take down from sun microsystems, microsoft, and others. You also have a copy of the SciFi novel writer, Michelle Sagara's home page in there which is really crazy. Oops. That was in the original package I got from Tom West, who is married to Michelle Sagara. I now notice that there is some libraries, mostly for images. I will look into their licenses. Confidential and copyrighted though? I don't know what code you mean by that.

 Author: Tony [ Sun Dec 04, 2011 6:42 pm ] Post subject: RE:DWITE io allotted time https://github.com/Open-Turing-Project/OpenTuring/blob/master/ready/src/jni/jawt.h Quote: /* * @(#)jawt.h 1.8 01/12/03 * * Copyright 2002 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */

 Author: trishume [ Mon Dec 05, 2011 4:11 pm ] Post subject: Re: DWITE io allotted time Friggin ready Java. Clutterin' up the code base. After I finish my application essay for Shad Valley I will go on a problem fixing blitz.

 Author: A.J [ Tue Dec 06, 2011 5:58 pm ] Post subject: RE:DWITE io allotted time Straying off topic guys...you keep giving me the hope that a post is somehow related to DWITE everytime a new post is made.

 Author: coolgod [ Wed Dec 07, 2011 1:20 am ] Post subject: Re: RE:DWITE io allotted time A.J @ Tue Dec 06, 2011 5:58 pm wrote:Straying off topic guys...you keep giving me the hope that a post is somehow related to DWITE everytime a new post is made. lol exactly. How is open turing even related to io anyways?

 :