Re: Serious bug inn GUILE rational handling

Re: Serious bug inn GUILE rational handling

[Bill Schottstaedt]

> I have removed support for the reduced bit, and put the reduction in
> make_fraction.

I think it was intended that equal? would use scm_i_fraction_equalp
which reduces both arguments before checking equality.  So the
simplest fix would be to mask off the reduced bit in the cell type
in the check for cell type equality in scm_equalp.  I would hesitate
to remove support for this bit because it will mean you get gcd
on every integer divide!  The current system already slows Guile
down by about 10%.   On the race condition, my vage recollection
is that the "is this safe?" question was mine, and I hoped at that
time that someone who knew about such things would check it
out -- I believe (it's been a long time since I looked at this stuff)
that if that line is not safe, there are a lot more like it scattered
around Guile, so it's scarcely reason to jettison the entire thing.



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: Serious bug inn GUILE rational handling

[Han-Wen Nienhuys]

Bill Schottstaedt escreveu:
>> I have removed support for the reduced bit, and put the reduction in
>> make_fraction.
> 
> I think it was intended that equal? would use scm_i_fraction_equalp
> which reduces both arguments before checking equality.  So the
> simplest fix would be to mask off the reduced bit in the cell type
> in the check for cell type equality in scm_equalp.  I would hesitate
> to remove support for this bit because it will mean you get gcd
> on every integer divide!  The current system already slows Guile

I think thes best quick fix would be to put the bit into the 4th 
double cell word. 

> down by about 10%.   On the race condition, my vage recollection
> is that the "is this safe?" question was mine, and I hoped at that
> time that someone who knew about such things would check it
> out -- I believe (it's been a long time since I looked at this stuff)
> that if that line is not safe, there are a lot more like it scattered
> around Guile, so it's scarcely reason to jettison the entire thing.

In that case, we need to fix the more-like-it stuff.  Can you point out 
some of those cases? 

I'm hesitant to put stuff like this in because 

1. it _is_ a race condition

2. if it is triggered, it will be next to impossible to reproduce. In
effect this would lead to a once in a million inexplicable corruption.
And that's really bad.

The correct solution would be a to use a lock-free instruction to 
swap the old and reduced forms, but I'm not sure if we have those in 
GUILE.

As I explained earlier, the logic for doing reduces or not needs to be
more refined. Any program that does serious arithmetic in fractions 
will likely have exploding memory requirements.

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: Serious bug inn GUILE rational handling

[Han-Wen Nienhuys]

Han-Wen Nienhuys escreveu:
> Bill Schottstaedt escreveu:
>>> I have removed support for the reduced bit, and put the reduction in
>>> make_fraction.
>> I think it was intended that equal? would use scm_i_fraction_equalp
>> which reduces both arguments before checking equality.  So the
>> simplest fix would be to mask off the reduced bit in the cell type
>> in the check for cell type equality in scm_equalp.  I would hesitate
>> to remove support for this bit because it will mean you get gcd
>> on every integer divide!  The current system already slows Guile
> 
> I think thes best quick fix would be to put the bit into the 4th 
> double cell word. 

if the performance regression is serious, then we should do 
this for guile-1.8. 

where is the benchmark to measure this? 

>> down by about 10%.   On the race condition, my vage recollection
>> is that the "is this safe?" question was mine, and I hoped at that
>> time that someone who knew about such things would check it
>> out -- I believe (it's been a long time since I looked at this stuff)
>> that if that line is not safe, there are a lot more like it scattered
>> around Guile, so it's scarcely reason to jettison the entire thing.
> 
> In that case, we need to fix the more-like-it stuff.  Can you point out 
> some of those cases? 
> 
> I'm hesitant to put stuff like this in because 
> 
> 1. it _is_ a race condition

Note that this thing is also racing with any of the arithmetic instructions,
Suppose the reduce happens between
getting SCM_FRACTION_DENOMINATOR and SCM_FRACTION_NUMERATOR in scm_sum ?

Correct macros would extract both num and den atomically 
into temporary values.

> 2. if it is triggered, it will be next to impossible to reproduce. In
> effect this would lead to a once in a million inexplicable corruption.
> And that's really bad.
> 
> The correct solution would be a to use a lock-free instruction to 
> swap the old and reduced forms, but I'm not sure if we have those in 
> GUILE.

We seem to have something like it (FETCH_STORE) but no 
compare-exchange.

Glib's gatomic.c does have an enormous bunch of cmp & exch operations
in assembler for various platforms. 

Would it be an option to link GUILE to glib? 


-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: Serious bug inn GUILE rational handling

[Rob Browning]

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> We seem to have something like it (FETCH_STORE) but no
> compare-exchange.
>
> Glib's gatomic.c does have an enormous bunch of cmp & exch
> operations in assembler for various platforms.
>
> Would it be an option to link GUILE to glib?

Without having looked carefuly at what might be involved, if we do
decide that we might want atomic operations of some kind, then I think
I'd want to investigate how hard it might be to add the operations
directly to guile.

-- 
Rob Browning
rlb @defaultvalue.org and @debian.org; previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: Serious bug inn GUILE rational handling

[Kevin Ryde]

"Bill Schottstaedt" <bil@ccrma.Stanford.EDU> writes:
>
> On the race condition, my vage recollection
> is that the "is this safe?" question was mine,

Sorry if I tried to claim it when it was yours.  :-)

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
>
> In that case, we need to fix the more-like-it stuff.  Can you point out 
> some of those cases? 

I don't have any on my crib list, FWIW.  I remember symbol interning
looked worrying, unless that already got some attention.

> Correct macros would extract both num and den atomically 
> into temporary values.

2-word atomic read/write might be possible on i386 with the mmx or
floating point instructions, though a bit painful to setup.  Elsewhere
you could be in the realm of mutexes :(.

> Would it be an option to link GUILE to glib? 

That's the start of a slippery slope.  First it's "oh, lets use a bit
of glib", then it's "oh, gtk does nice menus", then it's "lets get the
gnome widgets", then before you know it your program won't even run
outside 100Mb of gnome desktop!  :-)


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: Serious bug inn GUILE rational handling

[Neil Jerram]

"Bill Schottstaedt" <bil@ccrma.Stanford.EDU> writes:

> in the check for cell type equality in scm_equalp.  I would hesitate
> to remove support for this bit because it will mean you get gcd
> on every integer divide!  The current system already slows Guile
> down by about 10%. 

Just to check: by "the current system" do you mean CVS after Han-Wen's
fix?

It would be good if you could post benchmark code for this.  It may be
that looking at that code would suggest a way of improving the fix.

Regards,
     Neil



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: Serious bug in GUILE rational handling

[Bill Schottstaedt]

I was talking about the original ratio implementation.  Much to my
surprise, I found no consistent timing difference before and after
the reduction change.  



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: Serious bug in GUILE rational handling

[Neil Jerram]

"Bill Schottstaedt" <bil@ccrma.Stanford.EDU> writes:

> I was talking about the original ratio implementation.  Much to my
> surprise, I found no consistent timing difference before and after
> the reduction change.  

That's good news, then.  Thanks for making the measurements.

Regards,
     Neil



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel