Fwd: Week 7 Update: Wikisort updates

Miles Fertel milesfertel at college.harvard.edu
Mon Jul 17 21:50:31 UTC 2017


Forgot to CC!
---------- Forwarded message ----------
From: Miles Fertel <milesfertel at college.harvard.edu>
Date: Mon, Jul 17, 2017 at 3:55 PM
Subject: Week 7 Update: Wikisort updates
To: Brooks Davis <brooks at freebsd.org>


Hey Brooks,

In this past week I have added 5 new types of tests:

   - Odd element sizes
      - Sorting an array of char[5] arrays
   - Big structs
      - Sorting structs of size greater than 400 Bytes
   - Pointers
      - Sorting an array of int*'s
   - Stability testing
      - Testing the ability of the algorithm to remain stable when sorting
      elements with identical values
   - Large element numbers
      - Sorting an array of ints with a length of every power of two from
      2^10 to 2^30

I also began work on the benchmarking script. Unfortunately, while testing
the benchmarking script with very large arrays, I noticed that my algorithm
fails when testing arrays of greater than 2^21 elements with a 512 int
cache. This problem is not present when using a dynamic buffer, but it is
likely just masking the issue, as it would be unable to happen with such
large buffer sizes.

In terms of benchmarking however, the generalized WikiSort appears to
maintain its improvement over the stdlib mergesort.

My benchmarking script, which was intended to be the goal the next two
weeks, should be ready for review tomorrow, and I will then shift my focus
to resolving the cache bug. At the same time, I will work on improving the
design of the testing framework. The reviews are located at:
WikiSort Tests <https://reviews.freebsd.org/D11621>
Wikisort <https://reviews.freebsd.org/D11598> (Will have to be updated as
bugs are resolved)

If you could recommend who I should add to the benchmarking script
phabricator review, that would be appreciated.

-Miles


More information about the soc-status mailing list