Re: simplify disksort, please review.

From: Antoine Brodin (antoine.brodin_at_laposte.net)
Date: 06/13/05

  • Next message: Jeremie Le Hen: "Re: Bug in #! processing - "pear broken on current"" 
    Date: Mon, 13 Jun 2005 13:26:21 +0200
To: Jeff Roberson <jroberson@chesapeake.net>

    Jeff Roberson <jroberson@chesapeake.net> wrote:
    > http://www.chesapeake.net/~jroberson/disksort.diff
    >
    > Our disksort algorithm used to be complicated by the BIO_ORDERED flag,
    > which could cause us to make some exceptions in the sorting. When the
    > ordered support was removed we never simplified the algorithm. The patch
    > above gets rid of the switch point and associated logic. It's now a
    > simple hinted insertion sort with a one way scan. Since it's a fairly
    > central algorithm, I'd appreciate a review.

    Sorry for the late review, but there's perhaps a problem:

    If you have this situation:

    queue:------------ 5 - 6 - 7
    last_offset: 4 |
    insert_point:------+

    And you bioq_disksort a bio with an offset of 1:

    queue:------------ 5 - 1 - 6 - 7
    last_offset: 4 |
    insert_point:------+

    It looks weirdly sorted.

    IIRC, the previous algorithm gave:

    queue:------------ 5 - 6 - 7 - 1

    Looking at revision 1.83, it looks like insert_point was useless, not
    switch_point.

    I can't test this change since disksort doesn't seem to be used by
    ata(4) anymore (is there any reason ?).

    Cheers,

    Antoine
    _______________________________________________
    freebsd-arch@freebsd.org mailing list
    http://lists.freebsd.org/mailman/listinfo/freebsd-arch
    To unsubscribe, send any mail to "freebsd-arch-unsubscribe@freebsd.org"

  • Next message: Jeremie Le Hen: "Re: Bug in #! processing - "pear broken on current""

    Relevant Pages

    • Re: qubits
      ... I also heartily recommend reading this review of the book: ... Deutsch created the first "killer app" for a quantum computer-an ... algorithm that depends upon qubit superposition. ... possible new highly intractable cryptographic keys. ...
      (comp.object)
    • Re: Commenting the source code.
      ... >> Comments often help me concentrate on what I'm doing. ... Well written code seldom needs any comments, if the algorithm used is ... There are exceptions, ... Dan Pop ...
      (comp.lang.c)
    • Re: Return or Not?
      ... Alwyn wrote: ... The designers of the STL, for better or worse, decided to ... > suppose, say that the algorithm has failed, but I would agree that the ... It must be evaluated on a case by case basis if exceptions ...
      (alt.comp.lang.learn.c-cpp)
    • Berlekamps algorithm
      ... I'm trying to implement Berlekamp's algorithm. ... irreducible polynomials." ... I've found quite a few exceptions, and here are one of them: ... But the null space basis has dimension 3: ...
      (sci.math)
    • Re: Which STL algorithm?
      ... Exceptions aren't for normal returns. ... Not to mention the performance hit. ... > that to adapt an algorithm too complex or lengthy to duplicate, ... > poor performance of the algorithm that doesn't terminate ASAP is the whole ...
      (microsoft.public.vc.stl)