search

racket / data

Other
16 stars 23 forks source link

add heap-remove-eq! #17

Closed Metaxal closed 4 years ago

Metaxal commented 4 years ago

As promised, the PR for eq?-based removal.

I decided to keep the previous behaviour separated and add a separate function heap-remove-eq! because the caveats are different from heap-remove!.

Notes:

Happy to revise as requested.

rfindler commented 4 years ago

If you are removing contracts, shouldn't you add in the corresponding checks? (Or did you and I just missed it?)

Robby

On Sun, Jul 19, 2020 at 8:24 AM Laurent Orseau notifications@github.com wrote:

As promised, the PR for eq?-based removal.

I decided to keep the previous behaviour separated and add a separate function heap-remove-eq! because the caveats are different from heap-remove!.

Notes:

  • This also fixes a bug in a couple of examples in the docs.
  • I loosened the contracts of make-heap and vector->heap to avoid wrapper contracts, as the stress tests in #16 https://github.com/racket/data/pull/16 showed that this can be quite expensive.

Happy to revise as requested.

You can view, comment on, or merge this pull request online at:

https://github.com/racket/data/pull/17 Commit Summary

  • add heap-remove-eq!

File Changes

Patch Links:

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/racket/data/pull/17, or unsubscribe https://github.com/notifications/unsubscribe-auth/AADBNME7J6ZZ552GZBWLS7LR4LXYFANCNFSM4PBKL7XQ .

Metaxal commented 4 years ago

Previously, the contracts were like:

[make-heap (-> (and/c (procedure-arity-includes/c 2)    
                       (unconstrained-domain-> any/c))
               heap?)]

and now they are like:

 [make-heap (-> (procedure-arity-includes/c 2)
                heap?)]

So the only check that is removed is that the comparison procedure returns a single value, which was checked for every single comparison, which is very expensive.

Checking this does not seem worthwhile to me. Furthermore, in case the number of values is different from 1, the error message is:

result arity mismatch;
 expected number of values not received
  expected: 1
  received: 2
  values...:

while the source location is the comparator, which seems very reasonable to me. (which means that this check is already performed by core racket, hence enforcing the contract seems redundant.)

Don't you agree?

rfindler commented 4 years ago

If the error message were clearer that the problem was the comparator returned the wrong number of results (as opposed to some other kind of wrong number of values internally in the heap implementation), then yes, I would agree that this is good. It doesn't, however, if I understand correctly. But if I'm wrong somehow, can you show the full error message?

As far as fixing the performance goes, we can improve things for standard comparators (like <, say) by doing a better job in the contract system. If there user-defined comparators that the compiler doesn't know as much about, then fixing performance overhead probably requires a more significant amount of work.

Metaxal commented 4 years ago

This is the current behaviour. Is it good enough? Screenshot from 2020-07-19 16-18-55

rfindler commented 4 years ago

That looks like a special case in a few ways: it has errortrace enabled (which is a 3x or so slowdown!) and it has the error in an especially friendly way to the reporting. I guess that if you run in the command-line with racket it won't look so nice. Also, if you do this the error might get worse:

(define node<=? quotient/remainder)
Metaxal commented 4 years ago

Indeed the message is worse.

In that case, how about an unsafe submodule that provides everything without contracts?

rfindler commented 4 years ago

That makes sense to me, although maybe it should be /unsafe at the end (ala (require ffi/unsafe)).

Metaxal commented 4 years ago

Done. I also added some doc at the top of the doc page about complexity orders, please also check that you are happy with it.

rfindler commented 4 years ago

Thanks. I looked only at this one aspect of this -- I feel like @rmculpepper should really be the one to check this code, if he has time?

Metaxal commented 4 years ago

In the last commit, I also shuffled the order of the elements in the example for heap-sort because they were already sorted (before calling heap-sort).

Metaxal commented 4 years ago

Oh wait, I've just learned about #:unprotected-submodule (from 7.3.0.3) of contract-out. I'll change my code to use this instead.

Metaxal commented 4 years ago

All done. The global commit makes things easier to compare again, as the main code is back into heap.rkt.

rmculpepper commented 4 years ago

Thanks! There's one more issue with the error formatting, and then it looks ready to me.

Metaxal commented 4 years ago

Should be all good now!

rmculpepper commented 4 years ago

Merged, thanks!

Metaxal commented 4 years ago

Yay! \o/ Thank you all for your help!