Bizarre behaviour of 'qsort' call attempt 
Author Message
 Bizarre behaviour of 'qsort' call attempt

I have had a problem generically interfacing for the C library's qsort,
using gnat on Intel Linux.

The behavior is rather strange.  If I *add* a call to Text_IO.Put in
the Compar function, it sorts correctly, otherwise no sorting occurs.
Unfortunately the call to Put makes it sort too slowly :(

Any ideas? (I know there are sort routines in pure ada, but this is
an useful general problem to solve)

(maybe this should go to GNATCHAT or something... sorry, this has been
puzzling me for months)
--
Adrian Wrigley,
Vancouver, BC.

---------------qs.ads-----------
generic
   type Value_T is private;
   type Index_T is (<>);
   type ValueArray_T is array (Index_T range <>) of Value_T;
   with function "<" (Left : Value_T; Right : Value_T) return Boolean is <>;
procedure QS (A : in out ValueArray_T);
---------------qs.adb-----------
with Text_IO;
with Interfaces.C; use Interfaces.C;

procedure QS (A : in out ValueArray_T) is

   type Value_A is access Value_T;
   type CompareFunction_T is access function (Left : Value_A; Right : Value_A)
      return Boolean;

   function Compar (Left : Value_A; Right : Value_A) return Boolean is
      X : Boolean;
   begin
      X := Left.all < Right.all;

--      Text_IO.Put (""); -- This line needed (why?)!!!!!!!!!!!

      return X; -- actually this should be an Interfaces.C.Int really
   end Compar;

   procedure Mysort (Base   : ValueArray_T;
                     NMemb  : size_t; Size : Size_t;
                     Compar : CompareFunction_T);
   pragma Import (C, Mysort, "qsort");

begin
   Mysort (A, size_T (A'Length), size_T (Value_T'Size / 8), Compar'Access);
end QS;
-------------------sorttest.adb----------
with Text_IO;
with Interfaces.C;
with QS;

procedure SortTest is

   type Value is new Float;
   type ValueArray is array (Integer range <>) of Value;
   Numbers : ValueArray := (1.0, 3.0, 2.0);

   function "<" (A, B : Value) return Boolean is
   begin
      return Float (A) < Float (B);
   end "<";

   procedure Sort is new QS (Value, Integer, ValueArray, "<");

begin

   Sort (Numbers);
   for I in Numbers'Range loop
      Text_IO.Put_Line (Value'Image (Numbers (I)));
   end loop;

end SortTest;
------------------------------------------



Mon, 23 Dec 2002 03:00:00 GMT  
 Bizarre behaviour of 'qsort' call attempt
My guess: GNAT optimises the way of passing parameters and handling
stack when instanciating (it will differ if Value_T is an integer,
a float or a big record...). Your "Mysort" cannot guess it when calling
"Compar.all" . So you might be luckier if you interface when needed, with
known types... Or you could explicitely use pointers.
______________________________________________________
Gautier  --  http://members.xoom.com/gdemont/gsoft.htm


Mon, 23 Dec 2002 03:00:00 GMT  
 Bizarre behaviour of 'qsort' call attempt

Quote:
>    function Compar (Left : Value_A; Right : Value_A) return Boolean is

The comparison function that qsort takes does not return a "Boolean".
It's return value is an integer which returns <0, 0, or >0 when the
left argument is repectively less than, equal to, or greater than the
right one.

Quote:
>       X := Left.all < Right.all;

The only way this could even potentially work is if True was
represented by -1 (or something else negative), False by 1 (or
something else positive), and no two elements were equal.

Quote:
>    Mysort (A, size_T (A'Length), size_T (Value_T'Size / 8), Compar'Access);

Isn't there a more portable way to express the number of bits per byte
than by using a hardwired 8?


Mon, 23 Dec 2002 03:00:00 GMT  
 Bizarre behaviour of 'qsort' call attempt


Quote:

> >    function Compar (Left : Value_A; Right : Value_A) return Boolean is

> The comparison function that qsort takes does not return a "Boolean".
> It's return value is an integer which returns <0, 0, or >0 when the
> left argument is repectively less than, equal to, or greater than the
> right one.

> >       X := Left.all < Right.all;

> The only way this could even potentially work is if True was
> represented by -1 (or something else negative), False by 1 (or
> something else positive), and no two elements were equal.

> >    Mysort (A, size_T (A'Length), size_T (Value_T'Size / 8),
Compar'Access);

> Isn't there a more portable way to express the number of bits per byte
> than by using a hardwired 8?

Certainly.  One can use System.Storage_Unit;

And.. to guard against Value_T'Size not being an integer multiple of
System.Storage_Unit, and given that integer division truncates, I would use:

size_T ((Value_T'Size + System.Storage_Unit - 1) / System.Storage_Unit)



Mon, 23 Dec 2002 03:00:00 GMT  
 Bizarre behaviour of 'qsort' call attempt

Quote:


> >    function Compar (Left : Value_A; Right : Value_A) return Boolean is

> The comparison function that qsort takes does not return a "Boolean".
> It's return value is an integer which returns <0, 0, or >0 when the
> left argument is repectively less than, equal to, or greater than the
> right one.

> >       X := Left.all < Right.all;

> The only way this could even potentially work is if True was
> represented by -1 (or something else negative), False by 1 (or
> something else positive), and no two elements were equal.

This seems to fix it!

I had been thrown off track by the procedure working, when adding a Put_Line for
debugging purposes.  When I originally coded it, I was in a hurry, and moved
on when it (apparently) worked. (lame excuses!)

For completeness, I have included the revised version at the end.
Any more bugs in sight?

All I ask now is how can I get GNAT to inline the Sort procedure into
SortTest (eliminating the Sort code), and how to to get the "<" code
inlined into the Compar function?  I have tried various of the
Pragma Inline possibilities and compiler options, but none seem
to work for me at the moment :(  Its frustrating to have two extra
layers of function call over the "C" version of the code, even though
it now runs fast enough.

Thanks guys for debugging my code (please use the code below freely!)
--
Adrian Wrigley,
Vancouver, BC.

-------qs.ads--------
with Interfaces.C; use Interfaces.C;

generic
   type Value_T is private;
   type Index_T is (<>);
   type ValueArray_T is array (Index_T range <>) of Value_T;
   with function "<" (Left : Value_T; Right : Value_T) return Int is <>;
procedure QS (A : in out ValueArray_T);
-------qs.adb--------
with Text_IO;
with System;
with Interfaces.C; use Interfaces.C;

procedure QS (A : in out ValueArray_T) is

   type Value_A is access Value_T;
   type CompareFunction_T is access function (Left : Value_A; Right : Value_A) return Int;

   function Compar (Left : Value_A; Right : Value_A) return Int is
      pragma Suppress (Access_Check);
   begin
      return Left.all < Right.all;
   end Compar;

   procedure Mysort (Base   : ValueArray_T;
                     NMemb  : size_t;
                     Size   : size_t;
                     Compar : CompareFunction_T);
   pragma Import (C, Mysort, "qsort");

begin

   Mysort (A,
           size_T (A'Length),
           size_T ((Value_T'Size + System.Storage_Unit - 1) / System.Storage_Unit),
           Compar'Access);

end QS;
-------sorttest.adb--------
with Text_IO;
with Interfaces.C; use Interfaces.C;

with QS;

procedure SortTest is

   type Value is new Float;

   type ValueArray is array (Integer range <>) of Value;

   Numbers : ValueArray := (1.0, 3.0, 2.0, 5.3, 2.8, 2.0, 11.9, 1.1);

   function "<" (A, B : Value) return Interfaces.C.Int is
   begin
      if    Float (A) < Float (B) then return -1;
      elsif Float (A) > Float (B) then return  1;
      else return 0;
      end if;
   end "<";

   procedure Sort is new QS (Value, Integer, ValueArray, "<");

begin

   Sort (Numbers);

   for I in Numbers'Range loop
      Text_IO.Put_Line (Value'Image (Numbers (I)));
   end loop;

end SortTest;



Tue, 24 Dec 2002 03:00:00 GMT  
 Bizarre behaviour of 'qsort' call attempt


Quote:
> I have had a problem generically interfacing for the C
library's qsort,
> using gnat on Intel Linux.

Have a look at the heap sorts in the GNAT library. These use
a modified version of heap sort that halves the number of
comparisons, and is typically highly competitive with quick
sort in the average case, and of course FAR better in the
worst case.

The algorithm used is quite interesting, it is fully described
in these packages, or rather, more accurately, references are
given to full descriptions.

Sent via Deja.com http://www.deja.com/
Before you buy.



Sat, 28 Dec 2002 03:00:00 GMT  
 Bizarre behaviour of 'qsort' call attempt

Quote:



>> I have had a problem generically interfacing for the C
>library's qsort,
>> using gnat on Intel Linux.

>Have a look at the heap sorts in the GNAT library. These use
>a modified version of heap sort that halves the number of
>comparisons, and is typically highly competitive with quick
>sort in the average case, and of course FAR better in the
>worst case.

Which isn't relevant here - qsort isn't necessarily a
quick sort. Under Linux, it's a hybrid, using a merge
sort when that is more optimal (according to some quick
heuristics.) If speed is of import, you probably need
to benchmark them.

--

http/ftp: x8b4e53cd.dhcp.okstate.edu
It was starting to rain on the night that they cried forever,
It was blinding with snow on the night that they screamed goodbye.
        - Dio, "Rock and Roll Children"



Sat, 28 Dec 2002 03:00:00 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. Intermetric's Mitchell Gart's vain attempt to censor other's opinions

2. Clarifying 'after' behaviour

3. Undocumented file behaviour (mode='r+')

4. Behaviour of 'set'

5. Unexpected behaviour from the 'in' operator

6. : Very strange behaviour of 'puts -nonewline'

7. BUG:(?): button behaviour when 'disabled'.

8. Bizarre behaviour in a CPCS report

9. An Attempt to Formalise Dylan's Type System (Part 2)

10. An Attempt to Formalise Dylan's Type System (Part 1)

11. I'm currently attempting to create a 2D scrolling map based on GPS co-ordinates

12. DBI Error when attempting to pass Oracle's SYSDATE to a place hol der

 

 
Powered by phpBB® Forum Software