Mergesort Tests

[milesfertel_college.harvard.edu]

Summary

Test cases for the implementation of Wikisort

[ngie]

lib/libc/tests/stdlib/mergesort_test.c

40

Please don't do this. Use CFLAGS+= -I${.CURDIR:H:H} in the Makefile and use #include "stdlib/wiki.c" instead.

49

This can be computed via nitems(..) since the storage for the data type is a known value on the stack. It doesn't need to be a separate field.

339

(picking a random line): style(9) states that { for functions must begin on column 0, e.g.,

ATF_TC_BODY(bigstruct_WikiSort_test, tc)
{

370

• Why 50?
• Can this be a more descriptive #define?

484

An expected failure needs to be added to the testcase in lieu of this comment, e.g.,

(in small_elt_mergesort_test)

atf_tc_expect_fail("this will fail until new mergesort is completed");

don't break head's tests please.

lib/libc/tests/stdlib/test-sort.h

36–48

These are unnecessary stylistic regressions from style(9). Please revert them.

There are a number of style(9) regressions after this point. Please fix.

[asomers]

In general, I think your testcases need more description. For example, it's not clear to me what the real difference is between the trivial, misc, and ordering test are.

Did you create this revision by uploading a diff through the web interface? That's why there are all these "Context not available" lacunae. If you use php5-arcanist, you won't have those. Or if you insist on using the web interface, you can create the diff with "-C 9999".

lib/libc/tests/stdlib/mergesort_test.c

49

Actually, he's using this structure as a poor man's vector, where ELT_MAX is the maximum size, and len is the currenty size. It's fine as-is.

55

This should be static const

68

This would be clearer as a memcpy instead of a loop. The same pattern happens in other test cases, too.

70

s/mergesort/WikiSort here and in other test cases

75

Perhaps you should create a separate function for this assertion? It seems to get used in every testcase.

161

I can't tell for sure because part of the diff is missing, but it looks like you're testing the sort with randomly generated data. If so, you need to print the whole array on failure, or else it will be impossible to debug.

312

This part should probably be a separate test case.

371

Why skip 0 and 1?

387

Please wrap lines to 80 columns

396

should be static. Also, style(9) states that the function return type should be on one line, and the function name should be on the next,

403

should be static

468

Testing WikiSort with half a billion elements? How long does that take? This is going to run as part of the Kyua test suite. Most testcases should take no more than 5 minutes.

lib/libc/tests/stdlib/test-sort.h

36

Per style(9), the function name should begin a new line.

42

What's the purpose of this diff chunk?

47

Please add comments describing the purpose of each of these sort helpers.

125

Please comment this function.

142

Why are you changing initvector? It looks like you're just reindenting it.

[milesfertel_college.harvard.edu]

lib/libc/tests/stdlib/mergesort_test.c

75

The issue that I ran into with that is that the function would have to know the type of the elements in the arrays. I could check the entire array for equality but then it would fail to state where the difference occurs. Do you have any recommendations for that?

371

The practice was inherited from the old test suite, but I chose to keep it because 0 elements would have no output regardless of whether the function failed with a 0 element input (Which it doesn't), and 1 element arrays are already sorted (with stability) so it would have no use here.

484

I had the expect fail in earlier commits but I removed it as the WikiSort algorithm passed the test without failure. This hits on a challenge I've been having with writing these tests. Should I be writing them for testing my implementation, or should I be writing them for testing the hopefully eventually integrated mergesort update. If it's the latter, then I can't user mergesort as a reference, and need to add a stable sorting algorithm to test-sorts.h for reference.

lib/libc/tests/stdlib/test-sort.h

36–48

I apologize about the modifications to style. I've been using clang-format for simplicities sake but i'll go through and ensure the code meets style(9).

[ngie]

lib/libc/tests/stdlib/mergesort_test.c

484

Answering this item really quickly... in general, the test needs to be written to pass with whatever upstream (ci.freebsd.org) will run software wise. Once ^/head has been enhanced/fixed to work with your new code, the expected failure should be removed.

[milesfertel_college.harvard.edu]

Made many changes according to recommendations.

[asomers]

lib/libc/tests/stdlib/mergesort_test.c

75

What about a macro? Then you wouldn't need to know type information. Something like this:

#define check_array_eq(it, len, expected, actual) do { \
    for (it = 0; it < len; it++) \
        ATF_CHECK_MSG(
            actual[it] == expected[it], \
            "item at index %d didn't match: %d != %d", \
            k, actual[it], expected[it]); \
} while(0)
testvector[k], sresvector[k]);

595–612

Why not use memcpy here if you're going to use it elsewhere?

595–612

Another good candidate for memcpy

[milesfertel_college.harvard.edu]

lib/libc/tests/stdlib/mergesort_test.c

161

Do you think that the checks should be restructured to print out the whole array on failure? The standard I had been following up to this point has been to just print out incorrect indices, but I can see how that would be problematic with randomly generated data.

484

Okay, if this is the case then you're saying the file should be structured to just test mergesort? I'll need to find a new stable reference sorting routine.

595–612

Wouldn't that be a problem here because of the extra space in the structs? InitVector is just an array of integers so i'd have to generate a new array of random struct big's in order to do a memcpy.

595–612

Is it better design to generate a random array in one statement and the memcpy it into the two test arrays?

[asomers]

lib/libc/tests/stdlib/mergesort_test.c

161

Yes. For randomly generated tests, I don't see any other way.

484

I'm a little confused. Are you planning to add a wikisort(3) to FreeBSD? Or are you planning to update mergesort(3)? Or both? Or are you intending to replace mergesort's implementation with wikisort? If the latter, then this file should contain no references to WikiSort. It should just test the installed mergesort(3).

595–612

You're right. I glossed over the fact that struct big is different than the things you sorted in earlier tests.

595–612

Ehh, either way would be ok.

[brooks]

lib/libc/tests/stdlib/mergesort_test.c

484

The plan is to replace mergesort with wikisort, but we need to verify performance, memory use, and (maybe) code size are acceptable before doing so in all cases. It may be that very small systems end up continuing to use mergesort (unless they are CHERI systems were mergesort is broken and useless.)

595–612

Actually, the structs should be zeroed or (better) filled with some sort of patterned so we can verify they are copied correctly.

598

In addition to verifying that the values are in order, we should also verifying that the structs have some sort of sensible contents. See my comment above.

[ngie]

This change isn't complete (arc patch D11621 fails with my ^/head checkout). Please post the complete diff against ^/head to phabricator.

lib/libc/tests/stdlib/mergesort_test.c

484

milesfertel...: my comment involves stability of the FreeBSD test suite, but it also applies to testing in general for projects.

If you're adding new tests which exercise new code, but will fail until the enhancement/fix has been finished, please mark the testcase as an expected failure so it gets annotated properly. (if you weren't aware) Unexpected failures and broken testcases result in kyua/Jenkins test run failures. Having consistent failures reduces the value of the test runs over time because people pay attention to high-level results (did the test run pass or fail) more than low-level results (did that one testcase fail because of a code change, or because it's unreliable?).

If you have the feature enhancement/fix ready though (and it's just not in ^/head), please get someone to check that change in first, then check in the completed test without the expected failure, and remove the [now] misleading comment.

[milesfertel_college.harvard.edu]

Updated tests to reflect tests of the mergesort implementation and not WikiSort

[milesfertel_college.harvard.edu]

lib/libc/tests/stdlib/mergesort_test.c

415

For some reason this statement was required in order for the test case to register that it had failed. When the expect fail is used, the check_msg's aren't enough for it to register failure. Why is that? Should I use ATF_REQUIRE here instead?

[asomers]

lib/libc/tests/stdlib/mergesort_test.c

406–584

Why the change from rand to arc4random?

407

This test is still not going to be useful unless it prints the entire input array on failure.

415

You must be doing something wrong. If an ATF_CHECK_MSG fails, then the test fails. Perhaps the ATF_CHECK_MSG's aren't getting run?

[milesfertel_college.harvard.edu]

Added the canary for the bigstruct test. Unsure if DEADBEEF is the right value to use but it's adjustable. The only problem I have left is that of printing out the entire array on failure. I'm unsure of the proper way to do that. I could print both the input array and the improperly sorted array to stderr, but I worry about if that would be very painful to look over and find the problem. Just the input array would probably be enough to reproduce the bug, but should it be printed directly to STDOUT or STDERR or do I have to do it through some ATF_TC medium?

[milesfertel_college.harvard.edu]

lib/libc/tests/stdlib/mergesort_test.c

406–584

Wanted to be consistent with the use of arc4random_buf elsewhere.

598

Is this as well another place where I should print out the corrupted buffer or could that get excessive?

[milesfertel_college.harvard.edu]

@ngie I think I had a misunderstanding with what these diff's should represent. I had been updating the page with diff's against the previous commits I had posted, for review purposes. Is the standard protocol for this page to host a diff against freebsd head such that it could be directly applied?

[brooks]

In D11621#245925, @milesfertel_college.harvard.edu wrote:

@ngie I think I had a misunderstanding with what these diff's should represent. I had been updating the page with diff's against the previous commits I had posted, for review purposes. Is the standard protocol for this page to host a diff against freebsd head such that it could be directly applied?

Yes, these should be diffs against freebsd. Phabricator handles diffs between updates so uploading those isn't useful.

[milesfertel_college.harvard.edu]

Adjusted diff to be a proper diff with respect to head.