-r--r--r-- 9049 djbsort-20260127/doc/html/index.html raw
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<style type="text/css">
html{overflow-y:scroll;background-color:#012345}
body{font-family:"Noto Sans","Droid Sans","DejaVu Sans","Arial",sans-serif;line-height:1.5}
tt,code{background-color:#f0f0f0;font-family:"Noto Sans Mono","Droid Sans Mono","DejaVu Sans Mono","Courier New",monospace,sans-serif;font-size:1em;}
pre{margin-left:3em}
p,ul,ol,blockquote,pre{font-size:1.0em;line-height:1.6}
li p{font-size:1.0em}
blockquote p{font-size:1.0em}
h1{font-size:1.5em}
h2{font-size:1.3em}
h3{font-size:1.0em}
h1 a{text-decoration:none}
table{border-collapse:collapse}
th,td{border:1px solid black}
table a{text-decoration:none}
table tr{font-size:1.0em;line-height:1.6em}
table tr{font-size:1.0em;line-height:1.5}
tbody tr:nth-child(2n+1){background-color:#f0ffff}
tbody tr:nth-child(2n+2){background-color:#fffff0}
#headline{display:block;margin:0;padding:0;color:#ffffff;background-color:#012345}
#headline .text{font-weight:bold;font-size:1.0em}
#headline input{display:none}
#nav ul{margin:0;padding:0}
#nav li{list-style-type:none;margin:0;padding:0}
.navtop{padding-bottom:0.5em;font-weight:bold;font-size:1.0em}
.navtop{background-color:#012345;color:#ffffff}
#nav .here{background-color:#012345;color:#ffffff}
#nav .away{background-color:#012345;color:#ffffff}
#nav .away a{text-decoration:none;display:block;color:#ffffff}
#nav .away a:hover,.away a:active{text-decoration:underline}
#hidemenu{visibility:hidden;display:none;overflow:hidden;position:fixed;top:0;left:0;height:100%;width:100%}
.main{padding:5px}
.main{background-color:#ffffff}
.pagetitle{font-size:1.4em;font-weight:bold}
@media only screen and (min-width:512px) {
.navtop{padding-top:5px}
#headline{top:0;margin:0;width:160px;height:100%;position:fixed;overflow:auto}
#headline .noselect{display:none}
#headline #nav{visibility:visible;display:block;width:auto;height:auto}
.main{margin-left:170px}
#headline #hidemenu{visibility:hidden}
}
@media not screen and (min-width:512px) {
#headline .noselect{-webkit-user-select:none;-ms-user-select:none;user-select:none;}
#headline #nav #navbot{visibility:hidden;position:fixed;top:0;left:-70%;z-index:2;transition:0.2s;margin:0;padding:0}
#headline input:checked ~ #nav #navbot{height:100%;position:fixed;top:0;left:0;visibility:visible;display:block;box-sizing:border-box;-moz-box-sizing:border-box;-webkit-box-sizing:border-box;vertical-align:center;font-size:1.0em;width:70%;overflow:auto}
#headline input:checked ~ #hidemenu{visibility:visible;display:block;background:black;opacity:0.3;z-index:1}
}
</style>
<title>
djbsort: Intro</title>
</head>
<body>
<label id=headline>
<input type=checkbox />
<nav id=nav>
<div class=navtop>
<span class=noselect>≡</span>
djbsort</div>
<ul id=navbot>
<li class=here>Intro
</li><li class=away><a href=download.html>Download</a>
</li><li class=away><a href=install.html>Install</a>
</li><li class=away><a href=test.html>Test</a>
</li><li class=away><a href=api.html>API</a>
</li><li class=away><a href=speed.html>Speed</a>
</li><li class=away><a href=security.html>Security</a>
</li><li class=away><a href=verif.html>Verification</a>
</li><li class=away><a href=internals.html>Internals</a>
</li><li class=away><a href=license.html>License</a>
</li><li class=away><a href=refs.html>References</a>
</li><li class=away><a href=comparison.html>Comparison</a>
</li></ul></nav>
<div id=hidemenu></div>
</label>
<div class=main>
<div class=pagetitle>djbsort: Intro</div>
<p>djbsort is a software library
for sorting arrays
of <code>int32</code> or <code>uint32</code> or <code>float32</code>
or <code>int64</code> or <code>uint64</code> or <code>float64</code>.
It provides the following features:</p>
<ul>
<li>
<p><strong>Speed</strong>:
djbsort is the <a href="speed.html">fastest</a> sorting library available
for typical array sizes on typical Intel/AMD CPUs.</p>
</li>
<li>
<p><strong>Security</strong>:
djbsort is designed to be <a href="security.html">safe for cryptographic and non-cryptographic contexts</a>.</p>
</li>
<li>
<p><strong>Verification</strong>:
djbsort includes not just conventional tests but also tools to <a href="verif.html">automatically verify correctness</a>.</p>
</li>
</ul>
<p>These features are not separate options:
there is unified code providing all of these features simultaneously,
rather than separate <code>sort_fast</code> and <code>sort_secure</code> and <code>sort_verified</code> functions.</p>
<p>Latest release: <a href="download.html">20260127</a>.</p>
<h2>Limitations</h2>
<p>Interface limitations:</p>
<ul>
<li>
<p>This library is only for sorting numeric types.
Numeric types are important targets for sorting
(for example,
Google's vqsort paper <a href="https://arxiv.org/abs/2205.05982">reported</a>
that half of Google's <code>std::sort</code> calls were without specialized comparators,
and that integer-array sorting in particular was taking 2/3 of the total time for those calls)
but not the only targets for sorting.
To sort other data types,
you need to switch to another library.</p>
</li>
<li>
<p>This library is only for sorting memory-mapped data (for example, arrays that fit into RAM).
This is not an issue for typical 64-bit machines,
but means that a 32-bit machine cannot use this library to sort (e.g.) 10GB of numbers on disk.
The underlying techniques can be adapted to arrays stored on disk,
supporting a regular data-access pattern
along with standard techniques to further reduce disk accesses,
but the API does not directly support disks.</p>
</li>
</ul>
<p>Speed limitations:</p>
<ul>
<li>
<p>The speed is only for
CPUs with the AVX2 instruction set;
also, it does not take advantage of the AVX-512 instruction set
available on some CPUs.
However,
the underlying optimization techniques
can easily be ported to other CPUs.</p>
</li>
<li>
<p>For very large arrays, this library provides suboptimal latency,
in part because arrays are sorted using one core on one machine
and in part because the library uses sorting networks that scale as Θ(n log<sup>2</sup>n).
However, the underlying techniques can easily be parallelized
across cores and across machines.
Furthermore, applications that need top speed for very large arrays,
and that do not need the security advantages and verification advantages of sorting networks,
can use sorting networks up to a cutoff and then quicksort past the cutoff.
(This is already how various other libraries work,
but with small cutoffs since their sorting networks are not optimized as well as djbsort.)</p>
</li>
</ul>
<p>Verification limitations:</p>
<ul>
<li>
<p>The verification has been applied
to binaries produced by only a few compilers,
and is likely to need changes
to handle other compilers.
It is possible that the C code
has portability problems that damage correctness:
for example,
perhaps the C code triggers compiler bugs
on some platforms.</p>
</li>
<li>
<p>The verification is only for
the <code>int32</code> and <code>int64</code> sorting code.
The <code>uint</code> and <code>float</code> sorting code
consists of much smaller wrappers around the <code>int</code> sorting code,
but those wrappers could still have bugs that slip past tests;
the verification does not inspect those wrappers.</p>
</li>
<li>
<p>The verification does not check memory safety.
The <a href="test.html">tests</a> in djbsort include tests under valgrind,
but it is possible for memory-safety bugs to slip past valgrind.</p>
</li>
<li>
<p>The verification runs separately for each array size,
and becomes slower as the array size increases.
The verification has been run for many specific array sizes,
including some important array sizes for post-quantum cryptography,
but this does not guarantee correctness for other sizes.</p>
</li>
<li>
<p>The verification relies on large binary-analysis tools
and on djbsort's <a href="verif.html">sortverif</a> toolkit.
Bugs in sorting code could be hidden by bugs in these tools.</p>
</li>
</ul>
<h2>Credits</h2>
<p>The djbsort author is
<a href="https://cr.yp.to/djb.html">Daniel J. Bernstein</a>.</p>
<p>djbsort builds upon results from the following paper:
Daniel J. Bernstein, Chitchanok Chuengsatiansup, Tanja Lange, Christine van Vredendaal,
<a href="https://ntruprime.cr.yp.to/papers.html">"NTRU Prime: reducing attack surface at low cost"</a>,
Selected Areas in Cryptography 2017.
The NTRU Prime paper
explained how to make constant-time sorting software
run faster than Intel's Integrated Performance Primitives sorting software on Intel CPUs,
and demonstrated this with a software release in 2017.
djbsort includes verification and provides another 4x speedup.</p>
<p>See the list of
<a href="refs.html">references</a>
for related work.</p><hr><font size=1><b>Version:</b>
This is version 2026.01.26 of the "Intro" web page.
</font>
</div>
</body>
</html>