Replace insertion sort with hpsort in our kernel's qsort() function.
AbandonedPublic
Actions

Authored by • hselasky on Feb 10 2016, 12:15 PM.

Tags

None

Referenced Files

	Unknown Object (File)
	Wed, Sep 30, 6:51 PM

	Unknown Object (File)
	Wed, Sep 30, 6:50 PM

	Unknown Object (File)
	Wed, Sep 30, 5:24 PM

	Unknown Object (File)
	Tue, Sep 29, 1:59 AM

	Unknown Object (File)
	Tue, Sep 22, 11:34 PM

	Unknown Object (File)
	Sat, Sep 19, 11:50 AM

	Unknown Object (File)
	Sat, Sep 19, 11:47 AM

	Unknown Object (File)
	Sat, Sep 19, 11:44 AM

View All Files

Subscribers

imp

Details

Reviewers

rrs
gnn

Diff Detail

Repository

rS FreeBSD src repository - subversion

Lint

Lint Skipped

Unit

Tests Skipped

Event Timeline

• hselasky updated this revision to Diff 13178.Feb 10 2016, 12:15 PM

• hselasky retitled this revision from to Document the characteristics of our qsort() function..

• hselasky updated this object.

• hselasky edited the test plan for this revision. (Show Details)

• hselasky set the repository for this revision to rS FreeBSD src repository - subversion.

Herald added a subscriber: imp. · View Herald TranscriptFeb 10 2016, 12:15 PM

• hselasky added reviewers: rrs, gnn.Mar 31 2016, 9:17 AM

Don't use insertion sort which is O(N*N)

Use hpsort instead which is O(log2(N)*log2(N)*N).

I'm in private conversation with hps@ about this proposal.

This revision now requires changes to proceed.Apr 20 2016, 1:41 PM

• hselasky abandoned this revision.May 20 2016, 1:16 PM

Revision Contents
Changeset List

Path

Size

sys/

libkern/

qsort.c

130 lines

sys/

libkern.h

4 lines

Diff 15373

View Options

sys/libkern/qsort.c