Re: [Chicken-users] date comparison is very, very, very slow (srfi-19)

[Kon Lovett]

On Sep 24, 2008, at 9:04 PM, Alex Shinn wrote:

> Anthony Carrico <address@hidden> writes:
>
> > I ran into an extreme slowdown with some code that uses dates. I  
> > thought
> > this was a complexity issue with sorting, or something like that,  
> > but I
> > noticed that it was mainly GC, and traced it to date<?.
> >
> > Date comparison is done on julian-days, which are cached in dates,  
> > so it
> > is simplest to observe by running date->julian-day over
> > some random dates.
>
> Reasons in increasing order of relevance:
>
> 1) DATE->JULIAN-DAY is just in general an expensive
> operation, you want to avoid it in tight loops
>
> Hint: a custom comparator that compares dates field-by-field
> might be faster for sorting.

The SRFI 19 comparison routines could be rewritten in terms of such an  
algorithm. Currently defined in terms of the julian-day.

> 2) Record accessors in Chicken (and all Scheme
> implementations to my knowledge) are slow - they're not just
> memory references, but full procedures, and so every
> reference to every date field (all 8 of them) generates a
> generic procedure call with stack checking and all.

There is a sorta way around the above.

The "misc-extn" egg defines an 'inline-unchecked-record-type' where  
accessors are inlined procedures using compiler inlined '##sys#block'  
routines. These are used where an implementation will internally use  
the generated, private,  api & supply a public variant.

This hasn't been done for the SRFI 19 impl - yet.

> Hint: if you need to access a lot of fields at once, use
> MATCH, it's much faster:
>
>  (match date
>    (($ date nano sec min hour day mon year)
>     ...))
>
> 3) For some reason SRFI-19 uses the numbers egg

To match the domain of the SRFI 19 reference implementation.  
Specialized arithmetic is used where I could discern no violations.  
Otherwise the reference source prevails.

> - did you
> look at the output of date->julian-day?  It's an exact
> rational in the number of nanoseconds, and the date
> conversion performs a *lot* of numerical computations.
>
> Hint: use EXACT->INEXACT and the FP+, FP/, etc. floating
> point operators for a huge speedup, e.g.
>
>  (define (tm:julian-day nanosecond second minute hour day month year  
> tzo)
>    (fp+ (fp- (exact->inexact (tm:encode-julian-day-number day month  
> year))
>              0.5)
>         (fp/ (fp+ (exact->inexact
>                    (fx+ (fx+ (fx* hour SEC/HR)
>                              (fx+ (fx* minute SEC/MIN) second))
>                         (fxneg tzo)))
>                   (fp/ (exact->inexact nanosecond) 1000000000.0))
>              86400.0)))

Thank you for the inexact variant. Perhaps a compile-time and/or  
runtime switch can be made.

> --
> Alex
>
>
> _______________________________________________
> Chicken-users mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/chicken-users

Best Wishes,
Kon