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)
	Fri, Oct 18, 2:43 AM

	Unknown Object (File)
	Oct 10 2024, 7:00 PM

	Unknown Object (File)
	Oct 7 2024, 4:39 PM

	Unknown Object (File)
	Oct 7 2024, 10:35 AM

	Unknown Object (File)
	Oct 7 2024, 10:35 AM

	Unknown Object (File)
	Oct 7 2024, 10:35 AM

	Unknown Object (File)
	Oct 7 2024, 10:13 AM

	Unknown Object (File)
	Oct 4 2024, 2:17 PM

View All 63 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