Opened 3 years ago

Last modified 3 years ago

#20526 needs_info enhancement

A benchmarking tool for linear codes

Reported by: dlucas Owned by:
Priority: major Milestone: sage-7.3
Component: coding theory Keywords:
Cc: jsrn, cpernet Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: u/dlucas/benchmarking_tool (Commits) Commit: fe0b956386ad3fc684e5ae306254fb814fdc76e5
Dependencies: Stopgaps:

Description

This ticket proposes a tool to easily run experiments on linear codes (encoding, decoding...), gather data and process it.

Change History (19)

comment:1 Changed 3 years ago by dlucas

  • Branch set to u/dlucas/benchmarking_tool

comment:2 Changed 3 years ago by dlucas

  • Commit set to 5e18f8cc7ad80ea3fb65bbd311127633898378b6

I pushed the first version. Some minor issues still exist, I'll fix these in the next few days.


New commits:

cd86b18First version of a benchmarking tool for linear codes
5e18f8cAdded ticket number to experimental flag

comment:3 Changed 3 years ago by git

  • Commit changed from 5e18f8cc7ad80ea3fb65bbd311127633898378b6 to 8726309399d3e77214b98c66f2a093bba925d574

Branch pushed to git repo; I updated commit sha1. New commits:

8726309Changed how empty benchmarks are managed in __add__. Tweaks wrt. experimental_data

comment:4 Changed 3 years ago by dlucas

Hello,

I made some changes:

  • I removed the code, the encoder, the decoder and the channel from the dictionary experimental_data, as this never changes through the tests for a given benchmark.
  • I strengthened how empty benchmarks are managed in addition. Consider B1 and B2 two benchmarks. If:
    • B1 and B2 are empty, an exception is returned,
    • B1 or B2 are empty, the empty benchmark is ignored.

This is still under new state as there's some remaining bugs (e.g. "experimental" warning is called everytime a Benchmark is constructed, even inside the same session).

comment:5 Changed 3 years ago by jsrn

  • Cc jsrn cpernet added

comment:6 Changed 3 years ago by git

  • Commit changed from 8726309399d3e77214b98c66f2a093bba925d574 to 0ab93ecbf861c585b83bb162493afcaf5a2032c8

Branch pushed to git repo; I updated commit sha1. New commits:

5dafb07Removed encoder from constructor's input and made related adjustments in doc and methods
18732e1Adding two empty benchmarks now returns an empty benchmark
536ed61Added an extra message to _repr_ in case of an empty benchmark, enchanced docstring for _repr_
5030919Updated to 7.2rc1
32dd3d3no_tests is now a class argument, added related getter
0dfdbf0Replaced exception by a return statement in run() on empty benchmarks
7212b33Added a distinction between decoding_error and decoding_failure, refined decoding_success_rate accordingly
bc29f26Refined experimental_data method, which now allows request for specific data
a82a477Fixed syntax errors in documentation
0ab93ecChanges and fixes to docstrings and doctests

comment:7 Changed 3 years ago by dlucas

Hello,

Here's a change log for this ticket:

  • I removed encoder from this class. One cannot pass an encoder to a benchmark anymore, and all related methods have been deleted. Instead, I replaced the old call Benchmark(E, D, Chan) by Benchmark(C, D, Chan).
  • Adding two empty benchmarks now returns an empty benchmark and no longer an exception.
  • I added better messages in case one tries to manipulate an empty benchmark: for instance. calling Benchmark.run() now returns a proper message which explains that nothing will be done.
  • I refined the notion of "success rate". It now considers decoding errors (when the decoder fails at returning anything) and decoding failures (when the decoder returns a codeword which is not the expected one). I also enhanced decoding_success_rate, which now allows the user to select between success rate wrt. failures or errors.
  • I globally improved the documentation.

One problem remains: the experimental warning triggered by the decorator @experimental activates every time one creates a benchmark, which is annoying and also breaks all my doctests. This is quite weird as the documentation for this decorator says it will only be triggered once/session. Still investigating on this...

David

comment:8 Changed 3 years ago by jsrn

Sounds good! Quick remark (didn't check the code yet): In "A Course In Error-Correcting Codes" by Justesen and Høholdt then "decoding error" is defined as the decoder returning a codeword which was not the intended, and "decoding failure" is defined as the decoder not returning the wanted codeword (i.e. either returning nothing or returning a wrong one).

That is, P(failure) >= P(error) and P(failure) - P(error) = P(not returning anything).

Perhaps this implementation should reflect this (non-universally adopted) convention.

comment:9 Changed 3 years ago by git

  • Commit changed from 0ab93ecbf861c585b83bb162493afcaf5a2032c8 to d2d6e26916ea5157c8e1ae291859b10c077d94b9

Branch pushed to git repo; I updated commit sha1. New commits:

d2d6e26Improved data selection in experimental_data method

comment:10 Changed 3 years ago by git

  • Commit changed from d2d6e26916ea5157c8e1ae291859b10c077d94b9 to 8e363dd7ecf203cc4f203ea2b985573e4d59423c

Branch pushed to git repo; I updated commit sha1. New commits:

8e363ddSwitched definition of decoding error and decoding failure

comment:11 follow-up: Changed 3 years ago by dlucas

Hello,

Sounds good! Quick remark (didn't check the code yet): In "A Course In Error-Correcting Codes" by Justesen and Høholdt then "decoding error" is defined as the decoder returning a codeword which was not the intended, and "decoding failure" is defined as the decoder not returning the wanted codeword (i.e. either returning nothing or returning a wrong one).

Oops, I wanted to do that, but confused the definition of decoding error and decoding failure. Fixed now. BTW, the exception thrown when something wrong occurs during decoding is called DecodingError... Which is actually a bit confusing. But it follows the template to name exceptions.

David

comment:12 in reply to: ↑ 11 Changed 3 years ago by jsrn

BTW, the exception thrown when something wrong occurs during decoding is called DecodingError... Which is actually a bit confusing. But it follows the template to name exceptions.

Hmm, probably that's the reason I called that exception DecodingFailedError in Codinglib :-)

comment:13 follow-up: Changed 3 years ago by dlucas

Hmm, probably that's the reason I called that exception DecodingFailedError? in Codinglib :-)

Yes, that's much better! Do you think changing its name is worth the deprecation warning?

comment:14 Changed 3 years ago by jsrn

I've looked at the problem with the @experimental warning. The problem seems simply to be that (almost all) warnings in Sage currently issue a message *every* time the offending code is being run. Try LinearCode.decode for an example.

So why doesn't AsymptoticRing and friends behave like this with the @experimental warning? It's because all the classes inherit from UniqueRepresentation, so if multiple instantiations are called with the same arguments, the __init__ is actually only called once. This is why their TESTS block at the module top level turns off the FutureWarning in all the individual doc-tests later on.

I've asked about this on sage-devel: https://groups.google.com/forum/#!topic/sage-devel/RxMNjVWBeI0

Btw: how did I find out about this? I took the file growth_groups.py in sage.rings.asymptotic_ring, copied it and reduced it to a minimal working class that behaved well. Then I tried to remove code lines from it one-by-one until I found the line that made the doc-tests work. This turned out to be inheriting from UniqueRepresentation.

Best, Johan

comment:15 in reply to: ↑ 13 Changed 3 years ago by jsrn

Replying to dlucas:

Hmm, probably that's the reason I called that exception DecodingFailedError? in Codinglib :-)

Yes, that's much better! Do you think changing its name is worth the deprecation warning?

Hmm, how would you even deprecate this? Issue a deprecation warning only when the error is thrown?

But, thinking more about it, this name is also no good: the exception is used by a decoding algorithm when it realises that something went wrong, e.g. the polynomial division in Berlekamp-Welch doesn't go well. But this is exactly a case of DecodingFailure\DecodingError where \ indicates set difference; that is, it is a decoding failure that is surely not a decoding error (since no codeword is returned).

Justesen and Høholdt do not give a name to this event, but we need such a name for the decoding exception.

DecodingException? DecodeAbortError? DecodingAborted?

comment:16 Changed 3 years ago by jsrn

If you rebase on top of #20601 then all doc-tests pass now and the @experimental problem is gone.

comment:17 Changed 3 years ago by git

  • Commit changed from 8e363dd7ecf203cc4f203ea2b985573e4d59423c to fe0b956386ad3fc684e5ae306254fb814fdc76e5

Branch pushed to git repo; I updated commit sha1. New commits:

f967f59Make @experimental warnings issue only once
5c28822Added a test that in doc-tests demonstrates the behaviour
d14bdd4Sphinx link for 20601 and __experimental_self_test
fe0b956Merge branch 't/20601/20601_experimental' into benchmarking_tool

comment:18 Changed 3 years ago by dlucas

  • Milestone changed from sage-7.2 to sage-7.3
  • Status changed from new to needs_review

Hello,

If you rebase on top of #20601 then all doc-tests pass now and the @experimental problem is gone.

Thanks, it works fine!

This ticket is now open for review.

comment:19 Changed 3 years ago by jsrn

  • Status changed from needs_review to needs_info

This will probably be superseded by the BleacherMark project.

Note: See TracTickets for help on using tickets.