Home > Archive > Scheme > May 2004 > string-length speed
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
string-length speed
|
|
| Neil W. Van Dyke 2004-05-12, 9:13 pm |
| Is there any Scheme implementation in use that has a slow "string-length"
procedure?
By "slow," I mean that it has to perform an expensive count on each call
rather than simply regurgitating a string length number that's stored as
part of the internal representation of a string. If it counts once and
then caches for subsequent calls, that'd be OK.
(I actually have a good, practical reason for asking.)
| |
|
| "Neil W. Van Dyke" <neil@neilvandyke.org> wrote in message news:<584qqo2aze.fsf@neilvandyke.org>...
> Is there any Scheme implementation in use that has a slow "string-length"
> procedure?
>
> By "slow," I mean that it has to perform an expensive count on each call
> rather than simply regurgitating a string length number that's stored as
> part of the internal representation of a string. If it counts once and
> then caches for subsequent calls, that'd be OK.
Dunno. A Scheme implementation would do good in optimizing string
access, but of course Schemes that suffer from the UNICODE disease
might encode strings internally with multibyte character sequences
(but will probably keep a length slot separately as well).
IIRC, there is a paper by Shiro Kawai about these things.
In fact I just haven't got a clue, and just wanted to say something.
>
> (I actually have a good, practical reason for asking.)
(I'm really looking forward to get the answer to this...)
cheers,
felix
| |
| Martin Rodgers 2004-05-12, 9:13 pm |
| Neil W. Van Dyke wrote:
> Is there any Scheme implementation in use that has a slow "string-length"
> procedure?
>
> By "slow," I mean that it has to perform an expensive count on each call
> rather than simply regurgitating a string length number that's stored as
> part of the internal representation of a string. If it counts once and
> then caches for subsequent calls, that'd be OK.
>
> (I actually have a good, practical reason for asking.)
ISTR that Stalin uses C strings. They'll have to be counted at some
point, and that'll be at runtime in some programs. (Stalin can do very
impressive optimisations, including partial evaluation.) So the runtime
cost for some string-length calls can be O(N) instead of O(1).
I don't know if Stalin caches the length, but I expect that the cost
will depend on your coding style. For example, I tend to make the
caching explicit in my string processing code by saving the string
length in a local variable, as I almost always refer to the length again
shortly after the first use on a particular string, and then never
again. So the effective cost of Stalin's string-append in my code may be
much smaller in my code than in yours.
There may be other issues to consider.
--
http://www.wildcard.demon.co.uk You can never browse enough
Will write code that writes code that writes code for food
| |
| Jens Axel Søgaard 2004-05-12, 9:13 pm |
| Martin Rodgers wrote:
> ISTR that Stalin uses C strings.
Without checking I'd say that that sounds very unlikely.
Scheme strings can contain 0's whereas C strings can't.
--
Jens Axel Søgaard
| |
| Martin Rodgers 2004-05-12, 9:13 pm |
| Jens Axel Søgaard wrote:
> Martin Rodgers wrote:
>
>
>
> Without checking I'd say that that sounds very unlikely.
> Scheme strings can contain 0's whereas C strings can't.
ISTR reading in some docs that, where conformance conflicts with
performance, Stalin favours the latter. Checking the docs for Stalin
0.9, I find a list of deviations from R4RS, and a general point,
"Many of these simply are features that are not (yet) implemented though
I make no commitment to fully comply with R4RS and reserve the right to
deviate from R4RS for any reason whatsoever, particularly performance."
When in doubt, check the sourcecode. ;)
--
http://www.wildcard.demon.co.uk You can never browse enough
Will write code that writes code that writes code for food
| |
| Taylor Campbell 2004-05-12, 9:13 pm |
| Jens Axel Søgaard <usenet@soegaard.net> wrote in message news:<40a1005f$0$243$edfadb0f@dread11.news.tele.dk>...
> Martin Rodgers wrote:
>
>
> Without checking I'd say that that sounds very unlikely.
With checking, regardless of likeliness, it's true.
> Scheme strings can contain 0's whereas C strings can't.
Stalin strays from R5RS in much more significant ways than merely this
already.
| |
| Jeffrey Mark Siskind 2004-05-12, 9:13 pm |
| > Scheme strings can contain 0's
Not according to R4RS.
| |
| Jens Axel Søgaard 2004-05-12, 9:13 pm |
| Jeffrey Mark Siskind wrote:
[color=darkred]
> Not according to R4RS.
Ok - Now it makes sense.
--
Jens Axel Søgaard
|
|
|
|
|