From: David Kastrup <dak@gnu.org>
To: guile-devel@gnu.org
Subject: Re: Growable arrays?
Date: Tue, 12 Jun 2012 11:34:53 +0200 [thread overview]
Message-ID: <87mx48ooua.fsf@fencepost.gnu.org> (raw)
In-Reply-To: 87pq951k80.fsf@netris.org
Mark H Weaver <mhw@netris.org> writes:
> Hi David,
>
> David Kastrup <dak@gnu.org> writes:
>> I don't think I need yet another data structure deficient in some
>> respects. We have vectors that can't grow, hashtables that can grow but
>> only index through a hash function, vlists that can grow but have
>> immutable content...
> [...]
>> Why not just have a superset without arbitrary restriction and implement
>> the other structures based on that? Then each one just needs to enforce
>> its personal restrictions in its accessor functions, and otherwise just
>> use what is there in the general mechanism.
>
> Simpler data structures can usually be implemented with less memory,
> shorter code sequences with fewer conditional branches and less space in
> the instruction cache, which in turn means they can be implemented more
> efficiently. Therefore, to allow efficient compilation, primitive data
> structures should be very simple, with more complex structures built on
> simpler ones instead of the other way around.
>
> For example, consider resizable vectors vs fixed-size vectors. A
> fixed-size vector can be represented as a single memory block that
> contains both the length and the elements together. A resizable vector
> requires an additional level of pointer indirection, which inevitably
> means slower accesses and greater code size. Furthermore, fixed-size
> vectors allow the possibility of compiling in an unsafe mode where
> out-of-bounds checks can be skipped.
I have a really hard time swallowing an efficiency argument for Scheme
that is weak enough in comparison with the associated drawbacks not to
find consideration in the C++ standard template library. What kind of
performance gains are we talking about in a typical vector-heavy
application? 0.5%? Scheme is, to some degree, a computer theoretic
language. But in this case, this seems to me more like a "don't ask,
don't tell" scenario regarding the possibility of using one underlying
primitive type that dares to be a trifle more flexible than the
theoretically achievable minimum. Scheme implementations have
considerable leeway concerning their memory and data layout.
--
David Kastrup
next prev parent reply other threads:[~2012-06-12 9:34 UTC|newest]
Thread overview: 43+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-06-09 12:32 Growable arrays? David Kastrup
2012-06-09 14:43 ` Krister Svanlund
2012-06-09 17:35 ` David Kastrup
2012-06-11 4:23 ` Daniel Hartwig
2012-06-11 4:37 ` David Kastrup
2012-06-11 5:00 ` Daniel Hartwig
2012-06-11 7:25 ` David Kastrup
2012-06-11 9:01 ` Daniel Hartwig
2012-06-11 9:13 ` Daniel Hartwig
2012-06-11 10:38 ` David Kastrup
2012-06-11 11:57 ` Daniel Hartwig
2012-06-11 12:13 ` Noah Lavine
2012-06-11 12:28 ` David Kastrup
2012-06-11 23:50 ` Mark H Weaver
2012-06-12 9:34 ` David Kastrup [this message]
2012-06-12 20:34 ` Mark H Weaver
2012-06-12 20:47 ` David Kastrup
2012-06-12 21:03 ` Mark H Weaver
2012-06-12 21:18 ` David Kastrup
2012-06-11 8:14 ` Thien-Thi Nguyen
2012-06-11 9:08 ` Andy Wingo
2012-06-11 9:55 ` David Kastrup
2012-06-11 11:25 ` Andy Wingo
2012-06-11 12:00 ` David Kastrup
2012-06-11 12:12 ` David Kastrup
2012-06-11 12:20 ` David Kastrup
2012-06-11 13:04 ` Daniel Hartwig
2012-06-11 14:19 ` David Kastrup
2012-06-11 15:24 ` Stefan Israelsson Tampe
2012-06-11 15:27 ` Andy Wingo
2012-06-11 16:03 ` David Kastrup
2012-06-11 12:20 ` Daniel Hartwig
2012-06-11 12:36 ` David Kastrup
2012-06-11 12:02 ` Ludovic Courtès
2012-06-12 13:36 ` Hans Aberg
2012-06-14 14:33 ` Mark H Weaver
2012-06-14 14:47 ` David Kastrup
2012-06-14 15:23 ` Daniel Hartwig
2012-06-14 15:34 ` David Kastrup
2012-06-14 16:56 ` Daniel Hartwig
2012-06-14 17:15 ` David Kastrup
2012-06-14 17:23 ` Daniel Hartwig
2012-06-14 17:49 ` David Kastrup
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/guile/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87mx48ooua.fsf@fencepost.gnu.org \
--to=dak@gnu.org \
--cc=guile-devel@gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).