Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 DWITE io allotted time
Index -> CompSci.ca, Contests -> DWITE
Goto page 1, 2, 3  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
ttm




PostPosted: 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?
Sponsor
Sponsor
Sponsor
sponsor
ttm




PostPosted: Fri Dec 02, 2011 11:15 pm   Post subject: Re: DWITE io allotted time

Also latest binaries are here http://iobin.suspended-chord.info/.
chrisbrown




PostPosted: 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
Dan




PostPosted: 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.
Computer Science Canada Help with programming in C, C++, Java, PHP, Ruby, Turing, VB and more!
Insectoid




PostPosted: 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.
mirhagk




PostPosted: 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)?
Insectoid




PostPosted: 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.
mirhagk




PostPosted: 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....
Dan




PostPosted: 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.
Computer Science Canada Help with programming in C, C++, Java, PHP, Ruby, Turing, VB and more!
mirhagk




PostPosted: 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?
Tony




PostPosted: 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.
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
ttm




PostPosted: 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.
Dan




PostPosted: 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).
Computer Science Canada Help with programming in C, C++, Java, PHP, Ruby, Turing, VB and more!
trishume




PostPosted: 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.
mirhagk




PostPosted: 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)
Display posts from previous:   
   Index -> CompSci.ca, Contests -> DWITE
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 3  [ 36 Posts ]
Goto page 1, 2, 3  Next
Jump to:   


Style:  
Search: