[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Kon Lovett
Subject: Re: [Chicken-users] date comparison is very, very, very slow (srfi-19)
Date: Wed, 24 Sep 2008 21:38:45 -0700

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))
        (fp/ (fp+ (exact->inexact
                   (fx+ (fx+ (fx* hour SEC/HR)
                             (fx+ (fx* minute SEC/MIN) second))
                        (fxneg tzo)))
                  (fp/ (exact->inexact nanosecond) 1000000000.0))

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


Chicken-users mailing list

Best Wishes,

reply via email to

[Prev in Thread] Current Thread [Next in Thread]