A benchmarking tool for linear codes

[sagetrac-dlucas]

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

CC: @johanrosenkilde @ClementPernet

Component: coding theory

Branch/Commit: u/dlucas/benchmarking_tool @ fe0b956

Issue created by migration from https://trac.sagemath.org/ticket/20526

[sagetrac-dlucas]

Branch: u/dlucas/benchmarking_tool

[sagetrac-dlucas]

Commit: 5e18f8c

[sagetrac-dlucas]

comment:2

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

---

New commits:

cd86b18	First version of a benchmarking tool for linear codes
5e18f8c	Added ticket number to experimental flag

[sagetrac-git]

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

8726309

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

[sagetrac-git]

Changed commit from 5e18f8c to 8726309

[sagetrac-dlucas]

comment:4

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).

[sagetrac-git]

Changed commit from 8726309 to 0ab93ec

[sagetrac-git]

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

5dafb07	Removed encoder from constructor's input and made related adjustments in doc and methods
18732e1	Adding two empty benchmarks now returns an empty benchmark
536ed61	Added an extra message to `_repr_` in case of an empty benchmark, enchanced docstring for _repr_
5030919	Updated to 7.2rc1
32dd3d3	no_tests is now a class argument, added related getter
0dfdbf0	Replaced exception by a return statement in run() on empty benchmarks
7212b33	Added a distinction between decoding_error and decoding_failure, refined decoding_success_rate accordingly
bc29f26	Refined experimental_data method, which now allows request for specific data
a82a477	Fixed syntax errors in documentation
0ab93ec	Changes and fixes to docstrings and doctests

[sagetrac-dlucas]

comment:7

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

[johanrosenkilde]

comment:8

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.

[sagetrac-git]

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

d2d6e26

Improved data selection in experimental_data method

[sagetrac-git]

Changed commit from 0ab93ec to d2d6e26

[sagetrac-git]

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

8e363dd

Switched definition of decoding error and decoding failure

[sagetrac-git]

Changed commit from d2d6e26 to 8e363dd

[sagetrac-dlucas]

comment:11

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

[johanrosenkilde]

comment:12

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 :-)

[sagetrac-dlucas]

comment:13

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?

[johanrosenkilde]

comment:14

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

[johanrosenkilde]

comment:15

Replying to @sagetrac-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?

[johanrosenkilde]

comment:16

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

[sagetrac-git]

Changed commit from 8e363dd to fe0b956

[sagetrac-git]

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

f967f59	Make @experimental warnings issue only once
5c28822	Added a test that in doc-tests demonstrates the behaviour
d14bdd4	Sphinx link for 20601 and __experimental_self_test
fe0b956	Merge branch 't/20601/20601_experimental' into benchmarking_tool

[sagetrac-dlucas]

comment:18

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.

[johanrosenkilde]

comment:19

This will probably be superseded by the BleacherMark project.