Library Code Optimized?

This is a discussion on Library Code Optimized? within the C Programming forums, part of the General Programming Boards category; Does anyone know if the standard C library function qsort is pre-optimized? I am assuming the object code was compiled ...

  1. #1
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    320

    Library Code Optimized?

    Does anyone know if the standard C library function qsort is pre-optimized? I am assuming the object code was compiled using, say, gcc with a -O option.
    The reason I am asking is because I have to compare processing times for my homegrown quicksort function to the built-in qsort (which may or may not actually use quicksort). If I don't optimize I run 2-3 times slower than qsort, if I optimize fully, I run ~.7 seconds faster.

  2. #2
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by MacNilly View Post
    Does anyone know if the standard C library function qsort is pre-optimized? I am assuming the object code was compiled using, say, gcc with a -O option.
    The reason I am asking is because I have to compare processing times for my homegrown quicksort function to the built-in qsort (which may or may not actually use quicksort). If I don't optimize I run 2-3 times slower than qsort, if I optimize fully, I run ~.7 seconds faster.
    The C library is probably optimized, but not aggressively.

    Also, quoting sort time is kind of meaningless unless you specify the size of your data set. Make a graph of say, N = 10 to N = 10000 of the times for your sort vs. qsort(). That's a better way to see how you're doing.

    EDIT: Furthermore, test the performance of your sort on various distributions of values. What happens if the input is already sorted? Reverse-sorted? Consists all of a single value? Etc.
    Last edited by brewbuck; 11-01-2007 at 07:06 PM.

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I'd expect the c-library to be compiled with -O2 or -Os [which is essentially -O2 but with less inlining and unrolling]. That is in Linux. I haven't seen the build scripts for MS Libraries, but I would expect that they have decent optimization enabled.

    Is your own function using callbacks for compares, or are you comparing "inline"? If you are comparing inline, then that would help your function by a fair bit.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    320
    Since this is for a class assignment, I am required to use a callback for comparisons. Actually the parameters are exactly the same as qsort.

    The assignment only asks for a test of 1000 cases each sorting 20000 randomly-generated numbers. Since I am not using median-of-three or some other algorithm to select my pivot I am fairly sure that I will get O(N^2) on a already sorted list. Reverse sorted, probably the same. Although median of three is not required for this assignment, I am still thinking of a way to find the median item using only pointer arithmetic.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    That's pretty decent. I expect that if you use "fully optimized" as -O3, you'd get better results than the C library, since the latter has to compromise between "max" optimization and code-bloat, so it may not get quite as good optimization. Also, if you compile your function directly into the code, it may use more inlining than the C library can do - not sure about that. You could have a look at the generated code in your case, and compare it with the objdump of the C library function, of you really want to know where the difference is.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Property Set Library (PSL) - Announcement
    By vultur_gryphus in forum Projects and Job Recruitment
    Replies: 0
    Last Post: 05-29-2008, 06:04 AM
  2. very weird .h problem
    By royuco77 in forum C++ Programming
    Replies: 1
    Last Post: 09-11-2005, 07:55 AM
  3. Compiler Optimized code
    By Thantos in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 04-18-2004, 01:07 PM
  4. virtual library
    By spentdome in forum C Programming
    Replies: 0
    Last Post: 04-17-2002, 08:06 AM
  5. Replies: 4
    Last Post: 01-15-2002, 11:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21