Skip to content
New issue

Have a question about this project? # for a free GitHub account to open an issue and contact its maintainers and the community.

#

By clicking “#”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? # to your account

Jump to bottom

Scoring protocol does not timeout when scheme code has infinite loop #117

Open
greynotgrayskies opened this issue Aug 4, 2015 · 3 comments · May be fixed by #426
Open

Scoring protocol does not timeout when scheme code has infinite loop #117

greynotgrayskies opened this issue Aug 4, 2015 · 3 comments · May be fixed by #426
Assignees
@kavigupta

Comments

@greynotgrayskies
Copy link

If there's an infinite loop in scheme code that is tail-recursive, OK does not time it out, but continues to run indefinitely.
@greynotgrayskies
Copy link
Author

The problem is a bit more complex than I thought. For a solution like this, and the scoring protocol times out just fine:

(define (deep-map fn s)
        (deep-map fn s))

~/workspace/cs61a/grading/hw09$ python3 ok -q deep-map --score --local --no-update
=====================================================================
Assignment: Homework 9
OK, version v1.4.1
=====================================================================

Scoring tests

---------------------------------------------------------------------
deep-map > Suite 1 > Case 1

scm> (load 'hw09)

scm> (define (square x) (* x x))
square
scm> (deep-map square '(2 3))
# Error: evaluation exceeded 10 seconds.

# Error: expected
#     (4 9)
# but got
#     Timeout

---------------------------------------------------------------------
deep-map
    Passed: 0
    Failed: 1
[k..........] 0.0% passed

---------------------------------------------------------------------
Point breakdown
    deep-map: 0.0/1

Score:
    Total: 0.0

~/workspace/cs61a/grading/hw09$

However, this particular solution causes OK to hang indefinitely after grading. OK doesn't respond to a keyboard interrupt after this, so you have to terminate the process some other way:

(define (deep-map fn s)
  (cond ((null? s) nil)
      ((integer? (car s)) (deep-map fn (cons (fn (car s)) (cdr s))))
      ((list? (car s)) (deep-map fn (car s)))
  )     
)

~/workspace/cs61a/grading/hw09$ python3 ok -q deep-map --score --local --no-update
=====================================================================
Assignment: Homework 9
OK, version v1.4.1
=====================================================================

Scoring tests

---------------------------------------------------------------------
deep-map > Suite 1 > Case 1

scm> (load 'hw09)

scm> (define (square x) (* x x))
square
scm> (deep-map square '(2 3))
# Error: evaluation exceeded 10 seconds.

# Error: expected
#     (4 9)
# but got
#     Timeout


^C^C^C^Z
[1]+  Stopped                 python3 ok -q deep-map --score --local --no-update
~/workspace/cs61a/grading/hw09$ kill %1
[1]+  Terminated              python3 ok -q deep-map --score --local --no-update
~/workspace/cs61a/grading/hw09$

This also affects the normal grading protocol:

~/workspace/cs61a/grading/hw09$ python3 ok -q deep-map --local
=====================================================================
Assignment: Homework 9
OK, version v1.4.1
=====================================================================

Running tests

---------------------------------------------------------------------
deep-map > Suite 1 > Case 1

scm> (load 'hw09)

scm> (define (square x) (* x x))
square
scm> (deep-map square '(2 3))
# Error: evaluation exceeded 10 seconds.

# Error: expected
#     (4 9)
# but got
#     Timeout

^Z
[1]+  Stopped                 python3 ok -q deep-map --local
~/workspace/cs61a/grading/hw09$ kill %1
[1]+  Terminated              python3 ok -q deep-map --local

@kavigupta
Copy link
Contributor

Confirmed, repros on 1.14.19

@kavigupta kavigupta self-assigned this Dec 27, 2019
@kavigupta
Copy link
Contributor

I'm pretty sure this is related to memory usage. That specific piece of student code is equivalent to

(define (deep-map fn s)
  (deep-map fn (cons (fn (car s)) (cdr s))))

which, since the test case is (deep-map square '(2 3)), this is equivalent to (define (f x) (f (* x x))) (f 2). This leads to a repeated squaring of 2. On iteration i, this creates the number 2^(2^i), which takes 2^i bits to store. Empirically, the test case above uses all 8GB of my computer's memory and that causes the slowdown towards the end

I think the solution to this is probably to limit the memory usage of ok somehow.

@kavigupta kavigupta linked a pull request May 9, 2020 that will close this issue
Open
# for free to join this conversation on GitHub. Already have an account? # to comment
Assignees

@kavigupta kavigupta

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Add memory limit, defaulted to 1GB okpy/ok-client
2 participants
@kavigupta @greynotgrayskies