ASCIIZ strings in Forth
Len Zettel
a lot of string handling. After earnestly consulting my navel,
I have tentatively concluded that Ritchie et. al got it right -
strings with an end signaled by a special termination character are the way
to go. In Forth, the best termination character is binary zero, because
it can also serve a a flag.
I have seen such strings referred to as ASCIIZ. So I ask the community:
Is there available code for handling such & how can I get a look at it?
What naming conventions for such words are common?
trying to build on what has gone before
-LenZ-
Marcel Hendrix
>I have tentatively concluded that Ritchie et. al got it right -
>strings with an end signaled by a special termination character are the way
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>to go.
Can your navel expand on this a little bit? Up to now I've succeeded in ignoring the
variant (in non-GUI Forth code).
-marcel
Elizabeth D Rather
>a lot of string handling. After earnestly consulting my navel,
>strings with an end signaled by a special termination character are the way
>it can also serve a a flag.
>
>I have seen such strings referred to as ASCIIZ. So I ask the community:
>Is there available code for handling such & how can I get a look at it?
>What naming conventions for such words are common?
>
> trying to build on what has gone before
> -LenZ-
I'm far from enamoured of strings that have to be counted repeatedly at
run-time, but ASCIIZ strings are certainly ubiquitous in Windows, so
SwiftForth has a rich set of words for managing them (as well as counted
strings, addr-len strings, unicode strings, etc.). See Section 4.5.1 of the
SwF Ref Man for a glossary.
Summary:
Z" <string>" ( -- caddr ) Compile a string, returning its address at run
time.
Z\" <string>" ( -- caddr ) Same, but accepts control or other special chars
after \
,Z" <string>" ( -- ) Compile a string (outside a definition)
,Z\" <string>" ( -- ) Same, but accepts special chars after \
ZPLACE ( caddr1 u caddr2 -- ) Put the string caddr1 u at caddr2, as ASCIIZ
ZAPPEND ( caddr1 u caddr2 -- ) Append the string caddr1 u to the ASCIIZ
string at caddr2.
Cheers,
Elizabeth
he...@albany.net
zet...@acm.org wrote:
> Hogay, finally I am contemplating an application that will have
> a lot of string handling. After earnestly consulting my navel,
> I have tentatively concluded that Ritchie et. al got it right -
> strings with an end signaled by a special termination character are
the way
> to go. In Forth, the best termination character is binary zero,
because
> it can also serve a a flag.
Are you an innie or an outie? What words will you write that would
make one form of string better than another?
--
Leo Wong
he...@albany.net
http://www.albany.net/~hello/
The Forth Ring: http://zForth.com/
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
Julian V. Noble
> Hogay, finally I am contemplating an application that will have
> a lot of string handling. After earnestly consulting my navel,
> I have tentatively concluded that Ritchie et. al got it right -
> strings with an end signaled by a special termination character are the way
> to go. In Forth, the best termination character is binary zero, because
> it can also serve a a flag.
>
> Is there available code for handling such & how can I get a look at it?
> What naming conventions for such words are common?
>
> trying to build on what has gone before
> -LenZ-
HS/FORTH uses strings terminated by 00 and has words to do it with.
Although I no longer use that system, it does do that so it seems only
fair to mention it.
--
Julian V. Noble
j...@virginia.edu
"Elegance is for tailors!" -- Ludwig Boltzmann
Len Zettel
Elizabeth D Rather wrote:
>
(snip)
> I'm far from enamoured of strings that have to be counted repeatedly at
> run-time,
I am running on the premise that you don't have to count them at run time -
just set up a BEGIN ... WHILE or whatever that will handle them character by
character and stop at the end. As near as I can see (at first blush) the
only thing you lose is any system economies that might be built into MOVE.
And maybe some problems with ALLOCATE, which will only be done once, at
string creation time.
What you gain is the ability to handle strings of (virtually) unlimited
length with no storage penalty over counted strings and having to handle
one less stack argument.
> but ASCIIZ strings are certainly ubiquitous in Windows, so
> SwiftForth has a rich set of words for managing them (as well as counted
> strings, addr-len strings, unicode strings, etc.). See Section 4.5.1 of the
> SwF Ref Man for a glossary.
>
> Summary:
> Z" <string>" ( -- caddr ) Compile a string, returning its address at run
> time.
> Z\" <string>" ( -- caddr ) Same, but accepts control or other special chars
> after \
> ,Z" <string>" ( -- ) Compile a string (outside a definition)
> ,Z\" <string>" ( -- ) Same, but accepts special chars after \
> ZPLACE ( caddr1 u caddr2 -- ) Put the string caddr1 u at caddr2, as ASCIIZ
> ZAPPEND ( caddr1 u caddr2 -- ) Append the string caddr1 u to the ASCIIZ
> string at caddr2.
>
About all that's left is ZTYPE .
> Cheers,
> Elizabeth
Gary Chanson
>a lot of string handling. After earnestly consulting my navel,
>I have tentatively concluded that Ritchie et. al got it right -
>strings with an end signaled by a special termination character are the way
>to go. In Forth, the best termination character is binary zero, because
>it can also serve a a flag.
I disagree. The only time that ASCIIZ strings are preferable is
when you're interfacing with C and this can be dealt with by appending a
null to the end of a counted string. Counted strings perform significantly
better because you don't have to scan for the end of the string every time
you want to know how long it is.
I do all of my sting handling with a string stack package. The
strings on the stack have a 16 bit count and a trailing null.
Gary Chanson
>just set up a BEGIN ... WHILE or whatever that will handle them character
by
>character and stop at the end. As near as I can see (at first blush) the
>only thing you lose is any system economies that might be built into MOVE.
>And maybe some problems with ALLOCATE, which will only be done once, at
>string creation time.
Once you start dealing with strings, beyond the trivial uses that
most Forth programs get into, you'll find that there's a lot of dynamic
string manipulating involved.
>What you gain is the ability to handle strings of (virtually) unlimited
>length with no storage penalty over counted strings and having to handle
>one less stack argument.
A pointer to a counted string is only one argument (and not even
that with a string stack).
When was the last time you needed to deal with a string longer then
64K? When they get THAT large, they can be treated as special cases!
Bruce R. McFarling
<zet...@orchard.washtenaw.cc.mi.us> wrote:
>What you gain is the ability to handle strings of (virtually) unlimited
>length with no storage penalty over counted strings and having to handle
>one less stack argument.
Compared to ( ca u ) strings, don't you lose the ability to
handle substrings with the same words as you use for? And compared to
( ca u ) or counted strings, don't you lose the ability to embed
nulls? ...
Hmmm, the answer would seem to be that you lose those things
if you throw away both counted string and ( ca u ) words, but not if
you don't. I very much like the ability to reference a substring in
place without copy, but then one reason for permitting nulls in
strings is to use the null as a marker of some sort of structure in
the string, and handling the structured elements will then require
words to work with the null-delimited parts.
If you hold onto the ( ca u ) string handling and throw over
counted strings in favour of Z-strings, then one answer to the ZCOUNT
problem is that *in* the case that its a problem, use the ( ca u )
approach for it -- save the address and count as a double variable,
etc.
John Passaniti
Gary Chanson <gcha...@no.spam.shore.net> wrote in message
news:v6E23.637$nn.1...@news.shore.net...
> I disagree. The only time that ASCIIZ strings
> are preferable is when you're interfacing with C and
> this can be dealt with by appending a null to the end
> of a counted string. Counted strings perform significantly
> better because you don't have to scan for the end of
> the string every time you want to know how long it is.
>
> I do all of my sting handling with a string stack
> package. The strings on the stack have a 16 bit count
> and a trailing null.
There are advantages and disadvantages with both ASCIIZ strings and
counted strings. It all depends on what you need to do with your
strings.
Many people properly point out that if you want to know the length of
an ASCIIZ string, you have to count it. Of course, not every
operation regarding ASCIIZ strings requires counting. Say I merely
want to copy a string (usually the most common operation in many
programs that manipulate strings). Both ASCIIZ and counted strings
will result in code that is equally efficient. For ASCIIZ, you'll
grab a character from the source, store it at the destination, bump a
couple pointers, and compare against a terminating null in a loop.
For counted strings, you'll grab a character from the source, store it
at the destination, bump a couple of pointers, and compare against a
decrementing counter.
String comparisons are another example. Counted strings allow a quick
comparison of string lengths-- if they are different the strings are
different. But aside from that optimization, since you'll have to
iterate through the individual characters of the string anyway in both
ASCIIZ and counted strings, you end up with pretty much the same
thing.
Counted strings have the disadvantage of needing space to store the
count. Often when I am doing string processing, I freely process
strings larger than 64k, so I would probably want a 32-bit counter on
my counted strings. But that would be wasteful when I have many
smaller strings. ASCIIZ strings have the disadvantage of not being
able to store a null in the string, but have the advantage of only
needing a byte to store the terminator.
I for a while experimented with strings that had *both* a count and a
null terminator. This gave the best of both worlds-- operations that
iterated over the string could use the null. Operations that needed
to quickly address the end of the string could use the counts. Both
were kept in sync as the string length changed. It seemed like a good
idea-- but I eventually gave it up and used the style of strings that
was most appropriate for my application.
cLIeNUX operator
>Hogay, finally I am contemplating an application that will have
>a lot of string handling. After earnestly consulting my navel,
>I have tentatively concluded that Ritchie et. al got it right -
>strings with an end signaled by a special termination character are the way
>to go. In Forth, the best termination character is binary zero, because
>it can also serve a a flag.
>
>Is there available code for handling such & how can I get a look at it?
>What naming conventions for such words are common?
>
> trying to build on what has gone before
> -LenZ-
7 bit 0 is ASCII "NUL", null meaning "not a character" I suppose, and thus
If you build on this, you're building text. In Forth perhaps, "everything
is a word". Forth words like to be preceded by a count. Usually a count
byte. If string count words have bignum capability, then that count
generalizes to various file-like thingies.
Call it bellybutton lint.
Rick.
hmmmmm
#include <stdio.h>
void main(){printf("EOF = %d\n", EOF);}
returns -1.
he...@albany.net
zet...@acm.org wrote:
> Hogay, finally I am contemplating an application that will have
> a lot of string handling.
Steve McConnell's _Code Complete_ has a table of "The Best and
Worst Languages for Particular Kinds of Programs." He says, "The
classifications are broad, so take them with a grain of salt,
particularly if you know of specific exceptions."
For string manipulation the table lists:
Best Languages - Basic, Pascal
Worst Languages - C
Here's a possibly interesting passage from Abrash's _Zen of
Code Optimization_:
> The application we're going to examine searches a file for
> a specified string.
> ...
> The easiest approach would be to use a C/C++ library function.
> The closest match to what we need is strstr(), which searches
> one string for the first occurrence of a second string. However,
> while strstr() would work, it isn't ideal for our purposes.
> The problem is this: Where we want to search a fixed-length
> buffer for the first occurrence of a string, strstr() searches
> a _[z]string_ for the first occurrence of another string.
>
> We could put a zero byte at the end of our buffer to allow
> strstr() to work, but why bother? The strstr() function must
> spend time either checking for the end of the string being
> searched or determining the length of that string - wasted
> effort given that we already know exactly how long our search
> buffer is. Even if a given strstr() implementation is well-
> written, its performance will suffer, at least for our
> application, from unnecessary overhead.
>
> This illustrates why you shouldn't think of C/C++ library
> functions as black boxes; understand what they do and try
> to figure out how they do it, and relate that to their
> performance in the context you're interested in.
But what are you trying to do in Forth?
Len Zettel
John Passaniti wrote:
>
(snip)
> I for a while experimented with strings that had *both* a count and a
> null terminator. This gave the best of both worlds-- operations that
> iterated over the string could use the null. Operations that needed
> to quickly address the end of the string could use the counts. Both
> were kept in sync as the string length changed. It seemed like a good
> idea-- but I eventually gave it up and used the style of strings that
> was most appropriate for my application.
Very sensible. Would you mind sharing the words and stack effects of
your null-terminated string handling? So maybe we can build toward
common practice?
-LenZ-
Stephen Pelc
<UPK23.208$H5....@newsr1.twcny.rr.com>...
> I for a while experimented with strings that had *both* a count and a
> null terminator. This gave the best of both worlds-- operations that
> iterated over the string could use the null. Operations that needed
> to quickly address the end of the string could use the counts. Both
> were kept in sync as the string length changed. It seemed like a good
> idea-- but I eventually gave it up and used the style of strings that
> was most appropriate for my application.
--
Stephen Pelc, MicroProcessor Engineering - More real, less time
133 Hill Lane, Shirley, Southampton SO15 5AF, England
tel: +44 1703 631441, fax: +44 1703 339691, net: s...@mpeltd.demon.co.uk
web: http://www.mpeltd.demon.co.uk
Elizabeth D Rather
>
>
>Elizabeth D Rather wrote:
>>
>(snip)
>> I'm far from enamoured of strings that have to be counted repeatedly at
>> run-time,
>
>just set up a BEGIN ... WHILE or whatever that will handle them character
by
>character and stop at the end. As near as I can see (at first blush) the
>only thing you lose is any system economies that might be built into MOVE.
>And maybe some problems with ALLOCATE, which will only be done once, at
>string creation time.
Since MOVE is code in virtually all implementations, handling them
character-by-character in high level will be _lots_ slower, and if you're
contemplating long strings that's going to cost you big-time.
Cheers,
Elizabeth
Joel Rubin
<zet...@orchard.washtenaw.cc.mi.us> wrote:
>Hogay, finally I am contemplating an application that will have
>a lot of string handling. After earnestly consulting my navel,
>I have tentatively concluded that Ritchie et. al got it right -
>strings with an end signaled by a special termination character are the way
>to go. In Forth, the best termination character is binary zero, because
>it can also serve a a flag.
>
>I have seen such strings referred to as ASCIIZ. So I ask the community:
>Is there available code for handling such & how can I get a look at it?
>What naming conventions for such words are common?
>
Wouldn't most Forth's have something like this since most operating
systems use them? For example, the file API calls in MS-DOS, beginning
with version 2.0. Unless you want to build a general implementation,
there might be some advantage in finding out what you already have.
Bruce R. McFarling
OK, so:
if you're going to be moving them around, counted strings and
( ca u ) strings are more efficient;
if you are doing any complicated pattern matching, (ca-u)
strings let you avoid moving the strings around;
if you are using a substring of a string as a reference,
(ca-u) strings let you avoid moving the strings around;
if you want a distinctive marker embedded in your string,
(ca-u) and counted strings let you use the NUL character.
if you use a Zstring a lot, you will be moving it around, so
you will want to count it once for use and you will have to store the
count somewhere. When you fetch the count back, you will have a
(ca-u) string with an extra nul at the end.
The counter example which comes to my mind, where Zstrings are quite
possibly best, are in streams, where you can pass on bits of the
stream without having to say in advance how long a text string is
going to be -- and indeed without *discovering* how long the string is
until after you have been sending it for a while. After all, one way
to serialise a directory hierarhcy is to start with the topmost entry,
send its name as a Zstring, followed by the name of its contents as
Zstrings, with a null string closing a directory and starting the next
(the name is sent so that a subdirectory which has the name of the
contents of a previous directory can be recognised as a subdirectory).
Jerry Avins
>
> ...
>
> The counter example which comes to my mind, where Zstrings are quite
> possibly best, are in streams, where you can pass on bits of the
> stream without having to say in advance how long a text string is
> going to be -- and indeed without *discovering* how long the string is
> until after you have been sending it for a while. After all, one way
> send its name as a Zstring, followed by the name of its contents as
> Zstrings, with a null string closing a directory and starting the next
> (the name is sent so that a subdirectory which has the name of the
> contents of a previous directory can be recognised as a subdirectory).
I designed a few communications protocols and studied many more (looking
for ideas to copy). Without getting dogmatic with a word like "always",
I will say that it is unusual (when looking for reliability in
potentially noisy media) not to have a header thal includes a message
count, and some sort of checksum at the end. So I would immagine that
the streams you write of sending around never leave a particular
computer. But whether one uses Zstrings, Cstrings, or anything else, the
counts in external messages will be made by other software. Even the
count bytes will be counted.
Jerry
--
Engineering is the art | Let's talk about what
of making what you want | you need; you may see
from things you can get. | how to do without it.
---------------------------------------------------------
John Passaniti
Stephen Pelc <s...@mpeltd.demon.co.uk> wrote in message
news:01bea758$4fcdca80$0200a8c0@stephen...
> > I for a while experimented with strings that had *both* a
> > count and a null terminator. This gave the best of both
> > worlds-- operations that iterated over the string could
> > use the null. Operations that needed to quickly address
> > the end of the string could use the counts. Both were
> > kept in sync as the string length changed. It seemed like
> > a good idea-- but I eventually gave it up and used the
> > style of strings that was most appropriate for my application.
>
> Why?
Why what?
If you are asking why I experimented with a string model that combined
a count and a null terminator, it's because I could see the value in
both models, so I wanted to see what happened when I combined them.
It made some things easier (or at least to my mind clearer), and some
things harder (keeping the count updated was annoying. As I said, I
eventually gave up on that approach because the benefits were minor.
If you are asking why I now use a string model that is most
appropriate for my application-- either counted or null-terminated--
it's because of some of the reasons I stated before. I have written
applications that manage huge strings-- larger than 64k. For those
applications, counted strings with 32-bit counts works well. I have
also written applications that manage many short strings-- where the
overhead of a 32-bit count for each is costly. There I use a
null-terminated string.
As an aside, I'm now working on a project with very tight memory
constraints where I am representing strings using a Huffman-compressed
bit stream with a hash for each string. I need to store many strings
in a small amount of memory, but I also need to compare them quickly.
Since the cost of decompressing strings each time for simple
comparisons is high, the string representation I'm using is a 16-bit
hash of the string value (used only for comparisons) and a
variable-length bit stream for the string itself. If during a
comparison a hash matches, I decompress and compare. If the hash
doesn't match, I don't need to decompress. The Huffman tree is
static, using character frequencies that are typical of what I expect
to see.
Forth is a lot like C in that both languages don't really define a
string model. Sure, C's string literals are null-terminated, but
aside from that, the only reason most C applications use
null-terminated strings is because that's what the standard library
provides. Forth is much the same-- words like TYPE and NUMBER and
others presume counted strings, but you're not forced to adopt that
string model if it doesn't make sense for you application.
John Passaniti
Len Zettel <zet...@orchard.washtenaw.cc.mi.us> wrote in message
news:374BE86D...@orchard.washtenaw.cc.mi.us...
> Very sensible. Would you mind sharing the words
> and stack effects of your null-terminated string
> handling? So maybe we can build toward
> common practice?
Sure, although I'll probably get some knee-jerk reactions because the
names and semantics I chose come from the C string library. I've
simply found that the C string primitives work well for most (but not
all) of my needs, so in the interest of not spreading NIH syndrome, I
adopt instead of invent.
The only four original words I have are z", zalloc, zfree, and
zcreate. z" works as you might expect:
z" This is a string literal."
It compiles a null-terminated string and returns a pointer to it. I
do process C-style escape sequences.
zalloc and zfree allocate and deallocate null-terminated strings.
zalloc accepts a length on the stack, and returns either zero (for
failure) or a pointer to the string's allocated area. zfree accepts
either zero (where it does nothing) or a pointer to a
previously-allocated null-terminated string, and deallocates it.
zcreate takes a length on the stack and a word after it to form a
named null-terminated string object:
666 zcreate evil-string
Executing this would allocate a null-terminated string capable of
holding 666 characters, and create a word named "evil-string" that
returns the address of that string when executed. Nothing special or
exciting here. It does exactly what you think it would do.
For the words and stack effects, simply look at any man-page for
standard C library functions and interpolate. It's the same thing.
So for example, if you wanted to lexicographically compare "apples"
and "oranges" and see which was first, you would do this:
z" apples" z" oranges" strcmp
That would leave on the top of the stack what C would-- a number less
than zero, zero, or greater than zero to indicate the first string was
less than, equal to, or greater than the second string.
Or say you wanted to append the string "zealot" to the
previously-allocated evil-string, above:
evil-string z" zealot" strcat
This would return on the top of the stack what C would return from the
function call-- the address of the destination string with the string
appended.
This approach obviously has all the faults of C's string library. I
don't make any attempt to improve anything-- that would be done as a
layer on top of this model. The value here is familiarity. I can
show a C programmer how to work with these string routines far faster
than having them either create the words themselves, or having to
learn someone else's view of how strings should work.
Bruce R. McFarling
>Bruce R. McFarling wrote:
>> The counter example which comes to my mind, where Zstrings are quite
>> possibly best, are in streams, where you can pass on bits of the
>> stream without having to say in advance how long a text string is
>> going to be -- and indeed without *discovering* how long the string is
>> until after you have been sending it for a while. After all, one way
>> to serialise a directory hierarchy is to start with the topmost entry,
>> send its name as a Zstring, followed by the name of its contents as
>> Zstrings, with a null string closing a directory and starting the next
>> (the name is sent so that a subdirectory which has the name of the
>> contents of a previous directory can be recognised as a subdirectory).
>I designed a few communications protocols and studied many more (looking
>for ideas to copy). Without getting dogmatic with a word like "always",
>I will say that it is unusual (when looking for reliability in
>potentially noisy media) not to have a header thal includes a message
>count, and some sort of checksum at the end. So I would immagine that
>the streams you write of sending around never leave a particular
>computer. But whether one uses Zstrings, Cstrings, or anything else, the
>counts in external messages will be made by other software. Even the
>count bytes will be counted.
I don't disagree. More, I didn't disagree when I wrote what I
wrote. This is a distinction between communication information and
communicated information: an indefinite length string is still an
indefinite length string if its dispatched and recieved in chunks of
known size. If we specify packets, the freedom to be ignorant of the
string length is the freedom to be ignorant of exactly how many
packets are going to be sent when you start sending packets. That's
the difference between a generic stream and a generic file. For a
generic file, you can say "packet #i of #n", while for a generic
stream you can only say "packet #i".
Bruce R. McFarling
length range of traditional counted strings. For example, if string
space is allocated in chunks of 16 chars, then the count may be the
number of chunks, and a char counted string may be 4K chars long,
rather than 255 chars long---or a small Forth cell-counted string 1Mb
long, rather than 64K long. If they are text strings, and the final
chunk is padded with nulls (the final is important), then the exact
length can be determined by a four deep binary search for the first
null in the final chunk.
At the moment this is attracting me for BMW as as way to
represent text files in memory or in blocks, with each line headed by
the chunk-length of the previous and current line. For a simple
block-move-to-insert text editor, this reduces the block moves while
writing. And it gets rid of the seperate line array in favor of
variables to hold the first line, last line, and current line chunk
numbers. Further, it simplifies the task of mapping the memory-based
approach into blocks for small Forth systems, because chunk addresses
can map to: <block-group><block-in-group><chunk-in-block>.
Bernd Paysan
> Many people properly point out that if you want to know the length of
> an ASCIIZ string, you have to count it. Of course, not every
> operation regarding ASCIIZ strings requires counting. Say I merely
> want to copy a string (usually the most common operation in many
> programs that manipulate strings). Both ASCIIZ and counted strings
> will result in code that is equally efficient. For ASCIIZ, you'll
> grab a character from the source, store it at the destination, bump a
> couple pointers, and compare against a terminating null in a loop.
> For counted strings, you'll grab a character from the source, store it
> at the destination, bump a couple of pointers, and compare against a
> decrementing counter.
This is plain wrong. Moving a string with a known length can move larger
chunks and break down only for the last few bytes to a byte move. I.e. I
use rep movs on Intel processors, which calls highly optimized
microcode that reads in at least 64 bit at once, when source and target
are properly aligned. I'm not aware of a corresponding instruction that
calls highly optimized microcode for the ASCIIZ case.
The Alpha compiler has some optimizations for ASCIIZ strings that mainly
consist of SIMD instructions that test for a certain byte. One could use
the MMX instructions on newer Pentiums for that purpose, too, but it's
messy. Not nearly as easy as copying a known size of bytes.
One could say: the naive implementation of ASCIIZ and counted string
copy is equally slow.
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/
John Passaniti
Bernd Paysan <bernd....@gmx.de> wrote in message
news:37505D69...@gmx.de...
> This is plain wrong. Moving a string with a known
> length can move larger chunks and break down only
> for the last few bytes to a byte move.
Sure, for those processors that can address more than a byte at a
time. Let's not forget that many embedded systems programmers are
still pumping out code for 8-bit micros. Hell, I read that there are
more 8051's running code on the planet than any other microprocessor.
Forgive me for not exempting specific processors (like the 80x86) from
my previous statements.
> One could say: the naive implementation of ASCIIZ
> and counted string copy is equally slow.
Naive is only relative to a specific processor. I wasn't discussing
any specific processor.
Anton Ertl
"John Passaniti" <jp...@rochester.rr.com> writes:
> Say I merely
> want to copy a string (usually the most common operation in many
> programs that manipulate strings). Both ASCIIZ and counted strings
> will result in code that is equally efficient.
In a later posting you restrict this to a certain class of processors:
non-pipelined 8-bit processors (and I doubt that these do a lot of
string processing nowadays). You should have done so earlier.
If you have taken a look at computer architecture trends, you have
noticed that parallelism becomes more important over time, among other
things instruction-level parallelism. Given an explicit count, we can
copy the whole string in parallel. With 0-termination, we first need
to determine the length which takes log(length) steps with unlimited
resources.
Another problem with 0-termination is that it provokes buffer
overflows. To avoid this, you often have to determine the string
length first, which is cumbersome and inefficient.
And finally, you need to support both strings and other memory blocks;
if they have different implementations, as in C, you get two sets of
operations: strcmp-memcmp strcpy-memcpy etc.
So, in conclusion IMO Ritchie got this wrong, and ANS Forth 94 (which
strongly supported "addr u" strings) got it right.
- anton
--
M. Anton Ertl Some things have to be seen to be believed
an...@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html
Stephen C. Gilardi
> With 0-termination, we first need
> to determine the length which takes log(length) steps with unlimited
> resources.
Determining the length of a zero-terminated string appears to me to be
an O(length) operation. I looked a bit around the net for "optimize
strlen" and everything algorithm I saw was O(length).
Can you point me to a reference (or please explain) how it can be done
in O(log(length)) operations?
Thanks,
--Steve
--
Stephen C. Gilardi
SQ Software
Bruce R. McFarling
<jp...@rochester.rr.com> wrote:
>Bernd Paysan <bernd....@gmx.de> wrote in message
>news:37505D69...@gmx.de...
>> This is plain wrong. Moving a string with a known
>> length can move larger chunks and break down only
>> for the last few bytes to a byte move.
>Sure, for those processors that can address more than a byte at a
>time. Let's not forget that many embedded systems programmers are
>still pumping out code for 8-bit micros. Hell, I read that there are
>more 8051's running code on the planet than any other microprocessor.
>Forgive me for not exempting specific processors (like the 80x86) from
>my previous statements.
In the 65xx family, a zero delimited move (but the zero had
*better* be there -- otherwise it only halts if the target hits the
end of memory!) is:
ldy #0
- lda (source),y
sta (target),y
beq +
iny
bne -
inc source
inc target
bne -
+ rts
This is a win with strings up to a page, and then it starts to tip in
favour of the counted string. But with the 65816, the move
instructions make counted strings far better than zero delimited in
almost all circumstances.
.
Stephen C. Gilardi
> ldy #0
> - lda (source),y
> sta (target),y
> beq +
> iny
> bne -
> inc source
> inc target
> bne -
> + rts
It's been a long time since I 6502'd...
Shouldn't both "source" and "target" be increased by 256 (0x100) at the
bottom of the outer loop?
Does "inc source" increment source by 0x100? My recollection (which
could easily be wrong) is that "inc" increments the value stored at the
address specified by its argument by 1.
Andrew Haley
: Bernd Paysan <bernd....@gmx.de> wrote in message
: news:37505D69...@gmx.de...
: > This is plain wrong. Moving a string with a known
: > length can move larger chunks and break down only
: > for the last few bytes to a byte move.
: Sure, for those processors that can address more than a byte at a
: time. Let's not forget that many embedded systems programmers are
: still pumping out code for 8-bit micros. Hell, I read that there are
: more 8051's running code on the planet than any other microprocessor.
Right, but even on an 8051 it's faster to move strings around in
chunks of more than one byte at a time.
: Forgive me for not exempting specific processors (like the 80x86) from
: my previous statements.
I'm sure that there are microprocessors where there's no point in
moving strings around in chunks of greater than one byte, but I can't
say I've ever programmed one. 6502, perhaps? I've programmed one of
those, but it was a very long time ago.
Andrew.
Anton Ertl
The machine model I use has unlimited resources, but the operations
have only a fan-in of 2 (easy to generalize to greater, but limited
n):
1) compare every byte to zero, giving an array of numbers 0 (if the
byte is 0) or 1 (for non-zero). Set limit to 1.
2) If the first number is < limit, return it as result.
3) For every pair X,Y of numbers, compute:
X if X<limit
X+Y otherwise
Store the results in the array again.
Double limit.
Goto step 2.
After O(ld(length)) steps you are done.
E.g.: (with 0 representing the NUL character):
String: fjklsjfls00fklsdjf0dsa;
0: 11111111100111111101111
1: 2 2 2 2 1 0 2 2 2 0 2 1
2: 4 4 1 4 2 3
3: 8 1 2
4: 9 2
and the result is 9.
Bruce R. McFarling
Gilardi) wrote:
>Bruce R. McFarling <ec...@cc.newcastle.edu.au> wrote:
>
>> ldy #0
>> - lda (source),y
>> sta (target),y
>> beq +
>> iny
>> bne -
>> inc source+1
>> inc target+1
>> bne -
>> + rts
>
>It's been a long time since I 6502'd...
>
>Shouldn't both "source" and "target" be increased by 256 (0x100) at the
>bottom of the outer loop?
Right, left out the +1. I dashed that off before going home, so the
train schedule was setting how much time I spend on reviewing it.
Bruce R. McFarling
wrote:
If you have a count in COUNT and COUNT+1
LDY #0
CPY COUNT+1
BEQ +
- LDA (SOURCE),Y
STA (TARGET),Y
INY
BNE -
INC SOURCE+1
INC TARGET+1
DEC COUNT+1
BNE -
- LDA (SOURCE),Y
STA (TARGET),Y
INY
CPY COUNT
BNE -
RTS
By my reckoning, the zstring approach has an extra BEQ in the inner
loop, cost 2 cycles, and the count has an extra CPY COUNT in the
*final* inner loop, cost 3 cycles. So for moves under 2 pages, the
zstring is quicker, over, the counted string is quicker. Even quicker
is a counted zstring, which for a small test overhead at the beginning
saves 512 cycles per page on big block moves.
Of course, on the 65816 the block move blows that away, even
if it only moves things a byte at a time.
he...@albany.net
> : K 1024 * ;
>
> 20 K 2 + constant MAXLINE
> variable line MAXLINE chars allot
>
From: http://enki.lib.uchicago.edu/keith/crisis/benchmarks/fgrep/pfe.4th
Here's some explanation:
> The test run for the benchmark is:
>
> fgrep zygote /usr/dict/words
>
> On my system, /usr/dict/words is 206,672 bytes long and
> contains 25,144 lines, one word per line. zygote is the
> last word in the file.
The program uses READ-LINE. I can see swallowing large pieces
of a file in a buffer using READ-FILE. I ask two questions:
1. Is there a reason why the programmer wanted a 20 K buffer
to test his benchmark?
2. Would a larger than necessary buffer slow down (speed up?)
READ-LINE or does the size of the buffer not matter?
--
Leo Wong
he...@albany.net
http://www.albany.net/~hello/
The Forth Ring: http://zForth.com/
Sent via Deja.com http://www.deja.com/
John Passaniti
Andrew Haley <a...@cygnus.remove.co.uk> wrote in message
news:7j0tau$jqu$1...@korai.cygnus.co.uk...
> John Passaniti (jp...@rochester.rr.com) wrote:
> : Sure, for those processors that can address more than a
> : byte at a time. Let's not forget that many embedded systems
> : programmers are still pumping out code for 8-bit micros. Hell,
> : I read that there are more 8051's running code on the planet
> : than any other microprocessor.
>
> Right, but even on an 8051 it's faster to move strings around in
> chunks of more than one byte at a time.
Please detail the 8051 instructions which are used to move more than
one byte at a time. Unless you are talking about a weird derivative,
the straight 8051 instruction set only deals with byte-wide data
movements.
Marcel Hendrix
>I found this snippet in a Forth program:
>
>> : K 1024 * ;
>>
>> 20 K 2 + constant MAXLINE
>> variable line MAXLINE chars allot
>>
[..]
Hmm, looks familiar: LF, MF, HF :-?
BTW, K is used as an outer loop index in some Forths.
>The program uses READ-LINE. I can see swallowing large pieces
>of a file in a buffer using READ-FILE. I ask two questions:
>
>1. Is there a reason why the programmer wanted a 20 K buffer
> to test his benchmark?
This would depend on the implementation of READ-LINE. Under DOS, NT
and Linux I have not had much luck in finding system calls for unbuffered
reads of {cr lf} delimited lines. Therefore I suspect that in general a
Forth will attempt to read as many bytes as READ-LINE's user specifies
and then simply throws away what's not needed. Thus it is not wise to
specify excessively long lines.
In practice the OS may be smart enough to not really read the disk
unnecessarily (i.e read-again, caching and read-ahead), or the Forth may
do caching itself (iForth, Win32Forth). Doing caching in Forth is a problem
because it either involves calls to buffered system routines or necessitates
setting up a complex dynamically allocated buffer scheme (an unlimited
amount of files can be open at any one time, and R/W by the same or other
processes must be properly handled).
Finally, the READ-LINE arguments suggest there is no hidden buffering going
on and the user should optimize the size himself.
>2. Would a larger than necessary buffer slow down (speed up?)
> READ-LINE or does the size of the buffer not matter?
I think it will cause a slowdown for some Forths and almost never a
speedup. Maybe the large buffer is needed to read binary files?
-marcel
he...@albany.net
"Marcel Hendrix" <m.a.m....@ele.tue.nl> wrote:
> >
> >> : K 1024 * ;
>
> [snip]
>
> Hmm, looks familiar: LF, MF, HF :-?
>
No, from the source cited. Part of a rating of programming
languages in which Forth ends up last.
> BTW, K is used as an outer loop index in some Forths.
LF, etc. use:
: K* 1024 * ;
Thank you for the information in the rest of your discussion.
he...@albany.net
he...@albany.net wrote:
> LF, etc. use:
>
> : K* 1024 * ;
Maybe
: K* 10 LSHIFT ;
would be better?
Elizabeth D Rather
I assume he's meaning it's faster to use MOVE (written in code) rather than
a high-level loop doing C@ ... C! . On an 8051 it would be _lots_ faster.
Cheers,
Elizabeth
Marcel Hendrix
> In article <7j64a2$o...@news.tue.nl>,
> "Marcel Hendrix" <m.a.m....@ele.tue.nl> wrote:
>> >> : K 1024 * ;
[..]
>> Hmm, looks familiar: LF, MF, HF :-?
>>
> No, from the source cited. Part of a rating of programming
> languages in which Forth ends up last.
Not last by a mile, more middle-of-the-roadish. Before tcl and perl.
I can't reproduce the grep example because I don't have that file.
I rewrote tak and tested on a 166MHz Pentium.
Keith Waclena must have used a very slow machine, my timer says it takes
11 ms to execute.
-marcel
---
DOC
(* Unspecified machine...
+----------+----------------+-----------+---------------+----------------+
| Program | Run Time | Space | Compile Time | Source Size (K |
| | (secs) | (K) | (secs) | bytes) |
|----------|----------------|-----------|---------------|----------------|
| c | 0.067 | 258 | 1.02 | 0.61 |
|----------|----------------|-----------|---------------|----------------|
| this4th | 1.028 | 723 | NA | 1.22 |
|----------|----------------|-----------|---------------|----------------|
| perl | 9.086 | 4626 | NA | 0.37 |
|----------|----------------|-----------|---------------|----------------|
| tcl | 34.822 | 925 | NA | 0.34 |
+----------+----------------+-----------+---------------+----------------+
*)
ENDDOC
( takeuchi benchmark in ANS Forth )
( see <url:http://www.lib.uchicago.edu/keith/crisis/benchmarks/tak/> )
( Keith Waclena <k-wa...@uchicago.edu> )
: tak ( x y z -- t )
over 3 pick
>= IF nip nip
ELSE 2 pick 1- 2 pick 2 pick ( -- x-1 y z ) recurse >r
over 1- over 4 pick ( -- y-1 z x ) recurse >r
1- -rot ( -- z-1 x y ) recurse
2r> rot ( -- r1 r2 r3 ) recurse
ENDIF ;
: test CR TIMER-RESET -1
#100 0 DO drop #18 #12 6 tak LOOP
.ELAPSED SPACE . ;
\ FORTH> test
\ 1.099 seconds elapsed. 7 ok ( 11 ms )
Marcel Hendrix
> In article <1dsoig3.1fz...@ts002d14.nor-ct.concentric.net>,
> sque...@concentric.net (Stephen C. Gilardi) writes:
>> Determining the length of a zero-terminated string appears to me to be
>> an O(length) operation. I looked a bit around the net for "optimize
>> strlen" and everything algorithm I saw was O(length).
>> Can you point me to a reference (or please explain) how it can be done
>> in O(log(length)) operations?
> The machine model I use has unlimited resources, but the operations
> have only a fan-in of 2 (easy to generalize to greater, but limited n):
> 1) compare every byte to zero, giving an array of numbers 0 (if the
> byte is 0) or 1 (for non-zero). Set limit to 1.
Are you testing if we are still awake and reading your postings attentively,
or is this an example of the famous Austrian humor :-)
-marcel
John Passaniti
Elizabeth D Rather <era...@forth.com> wrote in message
news:7j6et4$qdt$1...@ash.prod.itd.earthlink.net...
> >> Right, but even on an 8051 it's faster to move strings around in
> >> chunks of more than one byte at a time.
> >
> >Please detail the 8051 instructions which are used to move more
than
> >one byte at a time. Unless you are talking about a weird
derivative,
> >the straight 8051 instruction set only deals with byte-wide data
> >movements.
>
> I assume he's meaning it's faster to use MOVE (written in code)
> rather than a high-level loop doing C@ ... C! . On an 8051 it
> would be _lots_ faster.
I thought the quote I responded to was unambiguous.
Regardless, I'm curious if there are any interesting optimizations
people have come up with to deal with null-terminated strings at the
Forth level, not at the application code level.
John Passaniti
Mary Murphy and Leo Wong <he...@albany.net> wrote in message
news:37573154...@news.albany.net...
> I was referring to:
>
> http://enki.lib.uchicago.edu/keith/crisis/langs/languages.html
Which is a great link to review and seriously think about.
The author uses a somewhat subjective rating system, and has
priorities that are probably not the same as many of the Forth fans in
this newsgroup. But hopefully people will be able to get past the
knee-jerk dismissal of the conclusions and look deeper are what are
real or perceived defects in Forth itself.
Forth fans should also study the language review and note (hopefully)
that the languages the author places higher are most commonly used in
different application domains than Forth is. One thing that I see
over and over in this newsgroup is the hidden assumption that everyone
in the world has the same set of priorities as embedded systems
programmers. Once you rise up over that assumption, you're likely to
at least see where the author's conclusions come from.
William Tanksley
>an...@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: ASCIIZ strings in Forth
>> The machine model I use has unlimited resources, but the operations
>> have only a fan-in of 2 (easy to generalize to greater, but limited n):
>> 1) compare every byte to zero, giving an array of numbers 0 (if the
>> byte is 0) or 1 (for non-zero). Set limit to 1.
>Are you testing if we are still awake and reading your postings attentively,
>or is this an example of the famous Austrian humor :-)
I did a double-take on that one as well. I _think_ that he's using a
machine which has one processor per byte of memory, so that the labelling
occurs in one cycle.
A pretty odd assumption, if you ask me. At least it should be listed
explicitly :).
>-marcel
--
-William "Billy" Tanksley
Utinam logica falsa tuam philosophiam totam suffodiant!
:-: May faulty logic undermine your entire philosophy!
Mary Murphy and Leo Wong
>he...@albany.net writes Re: Long Lines (Was: Re: ASCIIZ strings in Forth)
>
>> No, from the source cited. Part of a rating of programming
>> languages in which Forth ends up last.
>
>Not last by a mile, more middle-of-the-roadish. Before tcl and perl.
>I can't reproduce the grep example because I don't have that file.
>
I was referring to:
http://enki.lib.uchicago.edu/keith/crisis/langs/languages.html
Bernd Beuster
> : tak ( x y z -- t )
> over 3 pick
> >= IF nip nip
> ELSE 2 pick 1- 2 pick 2 pick ( -- x-1 y z ) recurse >r
> over 1- over 4 pick ( -- y-1 z x ) recurse >r
> 1- -rot ( -- z-1 x y ) recurse
> 2r> rot ( -- r1 r2 r3 ) recurse
> ENDIF ;
This one runs a bit faster on my maschine (Pentium/133MHz) with bigforth
and it doesn't need the ugly PICK ;-) :
: TAK ( x y z -- t )
>R 2DUP <= IF 2DROP R> EXIT THEN
OVER 1- OVER R@ RECURSE -ROT
2DUP 1- R@ ROT RECURSE -ROT
R> 1- -ROT RECURSE
RECURSE ;
old: 17.8 ms
new: 14.5 ms
--
Bernd
he...@albany.net
he...@albany.net wrote:
>
> 2. Would a larger than necessary buffer slow down (speed up?)
> READ-LINE or does the size of the buffer not matter?
>
A friend wrote: why don't you test it yourself?
( fgrep test in SwiftForth )
( after Keith Waclena <k-wa...@uchicago.edu> )
0 VALUE file-id
: make-work ( -- )
S" words.txt" R/W CREATE-FILE THROW TO file-id
26000 0 DO S" gamete" file-id WRITE-LINE THROW LOOP
S" zygote" file-id WRITE-LINE THROW
file-id CLOSE-FILE THROW ;
S" words.txt" FILE-STATUS NIP [IF] make-work [THEN]
: k* 1024 * ;
20 k* 2 + CONSTANT maxin
CREATE lpad maxin CHARS ALLOT
8 CONSTANT minin
\ Type if found
: ?FOUND ( a1 a1 a1 u1 a2 u2 -- )
SEARCH NIP NIP IF CR TYPE ELSE 2DROP THEN ;
0 VALUE nin
\ Search for pattern a u in file-lines
: fgrep ( a u -- )
R/O OPEN-FILE THROW TO file-id
2>R
BEGIN
lpad DUP nin file-id READ-LINE THROW
WHILE 2DUP 2R@ ?FOUND REPEAT 2DROP
2R> 2DROP
file-id CLOSE-FILE THROW ;
: test ( -- ) COUNTER
S" zygote" S" words.txt" fgrep
CR TIMER ." milleseconds " ;
: maxtest
maxin TO nin test ;
: mintest
minin TO nin test ;
mintest
maxtest
Results:
mintest 1648 milleseconds
maxtest 6352 milleseconds
Waclena reports running his own code in PFE in 1832 milleseconds.
I don't know how he did that. His code in SwiftForth took
6618 milleseconds on my machine (P2).
--
he...@albany.net
he...@albany.net wrote:
> milleseconds
milliseconds
And people want me to document my code.
Mille fleurs.
Anton Ertl
wtan...@dolphin.openprojects.net (William Tanksley) writes:
> On 3 Jun 1999 22:30:28 GMT, Marcel Hendrix wrote:
> >an...@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: ASCIIZ strings in Forth
>
> >> The machine model I use has unlimited resources, but the operations
> >> have only a fan-in of 2 (easy to generalize to greater, but limited n):
>
> >> 1) compare every byte to zero, giving an array of numbers 0 (if the
> >> byte is 0) or 1 (for non-zero). Set limit to 1.
>
> >Are you testing if we are still awake and reading your postings attentively,
> >or is this an example of the famous Austrian humor :-)
>
> I did a double-take on that one as well. I _think_ that he's using a
> machine which has one processor per byte of memory, so that the labelling
> occurs in one cycle.
Something like that; I was actually thinking of a superscalar
processor with an unlimited number of functional units etc.
SIMD-style instructions like the MMX extensions to the 386
architecture may also be sufficient for this example.
> A pretty odd assumption, if you ask me. At least it should be listed
> explicitly :).
It is: unlimited resources.
The original statement I made was about what is possible to do in
parallel. Using a machine model with infinite parallelism is quite
useful in exploring such questions.
What do we learn from this? With the trend towards more and more
instruction-level parallelism zero-terminated strings become more and
more inefficient compared to addr u strings.
Elizabeth D Rather
>Regardless, I'm curious if there are any interesting optimizations
>people have come up with to deal with null-terminated strings at the
>Forth level, not at the application code level.
For all the reasons cited in this thread, we prefer to use counted strings
and addr-len strings internally, but since Windows uses them heavily we
added the commands I described earlier, all of which are pretty
well-optimized.
Cheers,
Elizabeth
he...@albany.net
( fgrep in ANS-Forth )
( after Keith Waclena <k-wa...@uchicago.edu> )
\ Retreat to beginning of a line
: <LINE ( a u -- a' u' )
OVER DUP >R
BEGIN 1 CHARS - DUP C@ BL < UNTIL R> - 1+ /STRING ;
\ Find end of a line
: LINE> ( a u -- a' u' )
BEGIN DUP WHILE OVER C@ BL < 0= WHILE 1 /STRING REPEAT THEN ;
\ Find line, return line a2 u2 and remainder a1 u1
: <LINE> ( a u -- a1 u1 a2 u2 )
<LINE 2DUP 2>R LINE> DUP 2R> ROT - ;
\ Type found line
: found ( a u -- a' u' )
<LINE> CR TYPE ;
0 VALUE BUFFER
\ Search for pattern a1 u1 in lines of file a2 u2
: fgrep ( a1 u1 a2 u2 -- )
R/O OPEN-FILE THROW >R
R@ FILE-SIZE THROW D>S DUP 1 CHARS + ALLOCATE THROW TO BUFFER
BUFFER 0 OVER C! CHAR+ DUP ROT R@ READ-FILE THROW
2SWAP 2>R
BEGIN 2R@ SEARCH WHILE found REPEAT
2R> 2DROP 2DROP
BUFFER FREE THROW
R> CLOSE-FILE THROW ;
: test ( -- )
COUNTER
S" zygote" S" words.txt" fgrep
CR TIMER ." milliseconds" ;
test
Result: 176 milliseconds
Elizabeth D Rather
>
>
>The author uses a somewhat subjective rating system, and has
>priorities that are probably not the same as many of the Forth fans in
>this newsgroup. But hopefully people will be able to get past the
>knee-jerk dismissal of the conclusions and look deeper are what are
>real or perceived defects in Forth itself.
>
>Forth fans should also study the language review and note (hopefully)
>that the languages the author places higher are most commonly used in
>different application domains than Forth is. One thing that I see
>over and over in this newsgroup is the hidden assumption that everyone
>in the world has the same set of priorities as embedded systems
>programmers. Once you rise up over that assumption, you're likely to
>at least see where the author's conclusions come from.
I see tables, but no discussion (the one promising link, to "my language
crisis", was broken). He appears to have looked at two PD Forths written in
C for Unix and one book which many people found poorly-written and
confusing, so I find the exercise of limited value.
The fact is, Forth was originally designed for embedded systems, and has
been most successful there. A language is best evaluated in the context of
its design goals and target market. Just as folks today are encountering
much frustration attempting to use Java (designed for whizzy internet
graphics on big workstations) in embedded systems, it shouldn't surprise
anyone that a language designed for embedded systems should have some
shortcomings in a totally different context.
Cheers,
Elizabeth
he...@albany.net
"John Passaniti" <jp...@rochester.rr.com> wrote:
> [snip]
Waclena didn't do a Forth version of his invert benchmark
http://enki.lib.uchicago.edu/keith/crisis/benchmarks/invert/
saying,
> I was too lazy to write this benchmark in any language without
> an appropriate associative store and sequence sort.
Waclena thoughtfully provides the input and the desired output. I'm
sure Wil Baden will provide the appropriate Forth source.
Jerry Avins
>
> Elizabeth D Rather <era...@forth.com> wrote in message
> news:7j6et4$qdt$1...@ash.prod.itd.earthlink.net...
> > >> Right, but even on an 8051 it's faster to move strings around in
> > >> chunks of more than one byte at a time.
> > >
> > >Please detail the 8051 instructions which are used to move more
> than
> > >one byte at a time. Unless you are talking about a weird
> derivative,
> > >the straight 8051 instruction set only deals with byte-wide data
> > >movements.
> >
> > I assume he's meaning it's faster to use MOVE (written in code)
> > rather than a high-level loop doing C@ ... C! . On an 8051 it
> > would be _lots_ faster.
>
> I thought the quote I responded to was unambiguous.
Apparently not. My reading, biased by some familiarity with the machine
and an assumption that the remark wasn't idiotic, was that it is faster
to move strings when one knows either the character count or some value
that the count exceeds. It's hard to be truly unambiguous!
>
> Regardless, I'm curious if there are any interesting optimizations
> people have come up with to deal with null-terminated strings at the
> Forth level, not at the application code level.
Jerry
--
Engineering is the art | Let's talk about what
of making what you want | you need; you may see
from things you can get. | how to do without it.
---------------------------------------------------------
Anton Ertl
an interesting comparison of programming languages that is better done
than many I have seen. Forth is last, which is partly due to the
weights Keith Waclena assigns to various features (i.e., his
preferences), but partially because he does not give Forth the points
it deserves. I'll discuss the latter aspect in this posting.
The evaluation of Forth is at
http://enki.lib.uchicago.edu/keith/crisis/langs/Forth.html and the
criteria are explained in
http://enki.lib.uchicago.edu/keith/crisis/lang-features.html and
http://enki.lib.uchicago.edu/keith/crisis/imp-features.html.
> Feature Max Score Comments
> First-Class-Functions 100 0
You can take execution tokens (xts) of words, pass them around or
store them in any way, and finally EXECUTE or COPMPILE, them. They
are at least as powerful as C function pointers (C got 20 points in
this area).
Features over C: you can take the xt of any word, not just colon
definitions (with the exception of some standard words like IF); you
can COMPILE, xts, i.e. you can use it for run-time code generation.
You can also create anonymous colon definitions at run-time and pass
their xts around; this can be used to emulate currying and free
variables, but allocates dictionary storage that you have to free
explicitly.
> Modules 200 0
Wordlists (earlier known as vocabularies) give you separate
namespaces, and the search order wordset allows you to search them in
various ways. This can be used to build a variety of module systems,
but I have not found a useful one yet (but then I don't care for
module systems in other languages, either).
> Aggregates 200 10
> 10 points for the very cool CREATE DOES> construct.
It's mostly build-your-own using address arithmethic; if you are too
lazy for that, you can use existing packages, e.g., the structures in
http://www.complang.tuwien.ac.at/forth/objects/.
> Separate-Compilation 200 0
You can structure programs into several files (using INCLUDED),
without undue overhead; there is no standard way of path searching,
however.
> Objects 100 0
Also build-your-own. And there are lots of them, starting at 12 lines
(http://www.jwdt.com/~paysan/screenful.html).
> Memory-Mangement 200 0
A conservative garbage collector in standard Forth is available at
http://www.complang.tuwien.ac.at/forth/garbage-collection.zip.
> Recursion 200 50
> The ANS standard specifically provides an extremely small return stack.
This is wrong in two ways:
1) The standard guarantees a small return stack (at least I believe
so, I have trouble finding the place), whereas most other languages
don't guarantee anything. Any Forth on a decent machine will have a
decently sized (or user-specified) return stack. I have run Gforth
with 1400MB for each of its four stacks and the dictionary.
2) return addresses do not necessarily occupy the return stack, and if
they do, it is undefined how much space each return address takes. So
actually there is no guarantee, just as in other languages.
Two more notes: Forth makes it easy to do direct recursion in
anonymous words, and cumbersome to do mutual recursion.
> Posix 100 0
> Forth is extremely OS-hostile.
The standard says nothing about this, but neither does the C standard.
Concerning implementations, there are some around that have excellent
OS support (but the more portable ones are weaker here).
> Local-Functions 20 0
If you want them for non-local variables, you can emulate them by
run-time code generation, but you may not like the LIFO memory
management of these definitions.
> Macros 40 40
> CREATE DOES> combined with Forth's reflexivity is equivalent to an
> extremely powerful macro system.
I don't understand the comment. The way you do macros in Forth is
with IMMEDIATE, POSTPONE and LITERAL. You can use the full power of
the language in macro definitions, so IMO the rating is well-deserved.
> Syntax 30 30
> One of Forth's best features.
I'll quote that to everyone on c.l.f, who claims the syntax needs to
be improved:-)
> Pattern-Matching 50 0
There are several packages for doing this: FOSM, Brad Rodriguez'
backtracking parser, and Gray, a parser generator.
> Reflexivity 3 3
Somewhat neglected in the standard, though.
> Currying 9 0
You can emulate currying with CREATE-DOES> (see
http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/gforth_40.html#SEC46)
or with run-time code generation, i.e.:
: curry+ ( n -- xt )
>r :noname r> postpone literal postpone + postpone ; ;
1 curry+ 2 swap execute .
gives 3.
Wil Baden
> mintest 1648 milleseconds
> maxtest 6352 milleseconds
Your results look strange. Try them again. If they
come out similarly, check with Rick.
I ran mintest maxtest three times with the following results.
zygote
\ 0.79 sec milleseconds
zygote
\ 0.80 sec milleseconds
zygote
\ 0.79 sec milleseconds
zygote
\ 0.87 sec milleseconds
zygote
\ 0.90 sec milleseconds
zygote
\ 0.80 sec milleseconds
Sorting and Hanning the two sets of three gives .81 for both.
(: CR | 1<2<3 HANN . | ^ 79 79 90 ^^ 80 87 80 ^ :)
81
81
: 1<2<3 ( j k l -- j' k' l' )
2DUP > ?? SWAP
ROT 2DUP > IF SWAP
>R 2DUP > ?? SWAP R>
THEN
;
: HANN ( j k l -- m ) >R 2* + R> + 2 RSHIFT ;
In Unix, fgrep uses Boyer-Moore or Knuth-Morris-Pratt. For
this, a maximum buffer would definitely help when using READ-FILE.
--
Wil
Marcel Hendrix
> In article <7j3u46$qm0$1...@nnrp1.deja.com>,
> he...@albany.net wrote:
>>
>> 2. Would a larger than necessary buffer slow down (speed up?)
>> READ-LINE or does the size of the buffer not matter?
>>
> A friend wrote: why don't you test it yourself?
[.. code snipped ..]
> Results:
> mintest 1648 milleseconds
> maxtest 6352 milleseconds
[..]
I modified it a little so the size of overlong buffer can be studied.
Below are iForth's results. Don't make the buffer longer than
about 2 Kbytes. Mintest runs in 692 milliseconds.
-marcel
( fgrep test in iForth )
( after Keith Waclena <k-wa...@uchicago.edu> )
0 VALUE file-id
: make-work ( -- )
S" words.txt" R/W CREATE-FILE THROW TO file-id
26000 0 DO S" gamete" file-id WRITE-LINE THROW LOOP
S" zygote" file-id WRITE-LINE THROW
file-id CLOSE-FILE THROW ;
S" words.txt" FILE-STATUS NIP [IF] make-work [THEN]
0 VALUE nin
\ Type if found
: ?FOUND ( a1 a1 a1 u1 a2 u2 -- )
SEARCH NIP NIP IF CR TYPE ELSE 2DROP THEN ;
\ Search for pattern a u in file-lines
: fgrep ( a u -- )
nin CHARS ALLOCATE ?ALLOCATE LOCAL lpad
R/O OPEN-FILE THROW TO file-id
2>R
BEGIN
lpad DUP nin file-id READ-LINE THROW
WHILE 2DUP 2R@ ?FOUND REPEAT 2DROP
2R> 2DROP
file-id CLOSE-FILE THROW
lpad FREE ?ALLOCATE ;
: test ( -- )
TIMER-RESET S" zygote" S" words.txt" fgrep CR .ELAPSED SPACE nin . ;
: maxtest ( n -- ) TO nin test ;
\ (Leo) Results for SwiftForth:
\ mintest 1648 milleseconds
\ maxtest 6352 milleseconds
\ Waclena reports running his own code in PFE in 1832 milleseconds.
\ I don't know how he did that. His code in SwiftForth took
\ 6618 milleseconds on my machine (P2).
\ P2, 166 MHz.
FORTH> 8 maxtest
zygote
0.692 seconds elapsed. 8 ok
FORTH> 128 maxtest
zygote
1.310 seconds elapsed. 128 ok
FORTH> 256 maxtest
zygote
1.360 seconds elapsed. 256 ok
FORTH> 512 maxtest
zygote
1.434 seconds elapsed. 512 ok
FORTH> 1024 maxtest
zygote
1.624 seconds elapsed. 1024 ok
FORTH> 2048 maxtest
zygote
1.984 seconds elapsed. 2048 ok
FORTH> 4096 maxtest
zygote
2.711 seconds elapsed. 4096 ok
FORTH> 8192 maxtest
zygote
4.432 seconds elapsed. 8192 ok
FORTH> 16384 maxtest
zygote
7.908 seconds elapsed. 16384 ok
Marcel Hendrix
> Marcel Hendrix wrote:
>> : tak ( x y z -- t )
>> over 3 pick
>> >= IF nip nip
>> ELSE 2 pick 1- 2 pick 2 pick ( -- x-1 y z ) recurse >r
>> over 1- over 4 pick ( -- y-1 z x ) recurse >r
>> 1- -rot ( -- z-1 x y ) recurse
>> 2r> rot ( -- r1 r2 r3 ) recurse
>> ENDIF ;
> This one runs a bit faster on my maschine (Pentium/133MHz) with bigforth
> and it doesn't need the ugly PICK ;-) :
Contrary to what some Forthers may think, PICK is a very efficient
instruction.
> : TAK ( x y z -- t )
> >R 2DUP <= IF 2DROP R> EXIT THEN
> OVER 1- OVER R@ RECURSE -ROT
> 2DUP 1- R@ ROT RECURSE -ROT
> R> 1- -ROT RECURSE
> RECURSE ;
Aaaarrrgh... The EXIT enables the compiler to remove tail-recursion!
Why didn't I see that :-(
TAK runs in 10.666 milliseconds
: tak ( x y z -- t )
over 3 pick >= IF nip nip EXIT ENDIF
2 pick 1- 2 pick 2 pick ( -- x-1 y z ) recurse >r
over 1- over 4 pick ( -- y-1 z x ) recurse >r
1- -rot ( -- z-1 x y ) recurse
2r> rot ( -- r1 r2 r3 ) recurse ;
tak runs in 9.841 milliseconds (PICK may be ugly, but not slow).
-marcel
PS: I have no problem with Keith Waclena benchmarks. In fact I like
his pages, his Forth coding style, and the careful way he set up his
criteria. He evidently likes Forth and certainly has an open mind about
it. However, the way he *weighted* his criteria to end up with
a rating is totally subjective and IMHO not valid (even hilarious).
First decide on what you want to do, then choose the (best) language
for that purpose.
he...@albany.net
wilb...@netcom.com (Wil Baden) wrote:
> come out similarly, check with Rick.
>
Strange indeed. I'll try running the tests at home.
Thanks, Wil and Marcel.
Steven R. Wheeler
>
> John Passaniti wrote in message ...
> >
> >Mary Murphy and Leo Wong <he...@albany.net> wrote in message
> >news:37573154...@news.albany.net...
> >> I was referring to:
> >>
> >> http://enki.lib.uchicago.edu/keith/crisis/langs/languages.html
> >
> >Which is a great link to review and seriously think about.
> >
> >The author uses a somewhat subjective rating system, and has
> >priorities that are probably not the same as many of the Forth fans in
> >this newsgroup. But hopefully people will be able to get past the
> >knee-jerk dismissal of the conclusions and look deeper are what are
> >real or perceived defects in Forth itself.
> >
> >Forth fans should also study the language review and note (hopefully)
> >that the languages the author places higher are most commonly used in
> >different application domains than Forth is. One thing that I see
> >over and over in this newsgroup is the hidden assumption that everyone
> >in the world has the same set of priorities as embedded systems
> >programmers. Once you rise up over that assumption, you're likely to
> >at least see where the author's conclusions come from.
>
> I see tables, but no discussion (the one promising link, to "my language
> crisis", was broken). He appears to have looked at two PD Forths written in
> C for Unix and one book which many people found poorly-written and
> confusing, so I find the exercise of limited value.
The backlinks appear to be broken. If you go to:
http://enki.lib.uchicago.edu/keith/crisis/
it gets you to where the backlink would have taken you.
- wheels
Samuel A. Falvo II
>much frustration attempting to use Java (designed for whizzy internet
>graphics on big workstations) in embedded systems, it shouldn't surprise
Actually, no -- Java was (originally) designed for use in embedded
applications. It only found its true niche on the web, because Java was
inherently horrible for embedded work.
==========================================================================
KC5TJA/6 | -| TEAM DOLPHIN |-
DM13 | Samuel A. Falvo II
QRP-L #1447 | http://www.dolphin.openprojects.net
Oceanside, CA |......................................................
Helge Horch
>
>1) The standard guarantees a small return stack (at least I believe
>so, I have trouble finding the place), whereas most other languages
>don't guarantee anything.
I'll admit I only have a copy of the widely circulated public draft,
but I can't find anything in that regard either. All I found was
3.2.3.3, which mentions several restrictions, 3.2.6 introduces the
RETURN-STACK-CELLS selector for ENVIRONMENT? queries, and 4.1.3
requires the system to document the available depth.
What did I miss?
>> Macros 40 40
>> CREATE DOES> combined with Forth's reflexivity is equivalent to an
>> extremely powerful macro system.
>
>I don't understand the comment. The way you do macros in Forth is
>with IMMEDIATE, POSTPONE and LITERAL. You can use the full power of
>the language in macro definitions, so IMO the rating is well-deserved.
I'd second the rating, but I have also added Wil's MACRO (which uses
EVALUATE) to my tool set.
--
You read a scroll of "postpone until Monday at 9 AM".--more--
Everything goes dark...
Wil Baden
\ Using already written tools.
VARIABLE B-FILE
SRC MENU \ Attach inputdata to SRC file.
:GO BEGIN SRC READ WHILE ( str .)
2DUP BL SCAN SPLIT ( b . a .) 2SWAP ( a . b .) BL SKIP
CELL RESERVED B-FILE ADD-ITEM ( a . link)
COUNT+ 0 RESERVED ADD ( )
REPEAT ; GO
:GO B-FILE BEGIN DUP @ DUP WHILE + ( b-link)
CR DUP CELL+ COUNT TYPE
DUP CELL+ COUNT+ BEGIN DUP @ DUP WHILE + ( b-link a-link)
#TAB EMIT DUP CELL+ COUNT TYPE ( b-link)
REPEAT 2DROP
REPEAT 2DROP ( ) CR ; GO
Andrew Haley
: Mary Murphy and Leo Wong <he...@albany.net> wrote in message
: news:37573154...@news.albany.net...
: > I was referring to:
: >
: > http://enki.lib.uchicago.edu/keith/crisis/langs/languages.html
: Which is a great link to review and seriously think about.
Seriously to think about? It's an interesting and sometimes amusingly
eccentric comparison of programming languages, but I don't think that
it's intended to be taken very seriously. The method used to rank
languages is bound to result in the highest score going to the
language with the greatest number of features, which is hardly a
sensible way to design programming languages.
In the real world, sadly, this method is often used...
: The author uses a somewhat subjective rating system, and has
: priorities that are probably not the same as many of the Forth fans in
: this newsgroup. But hopefully people will be able to get past the
: knee-jerk dismissal of the conclusions and look deeper are what are
: real or perceived defects in Forth itself.
: Forth fans should also study the language review and note (hopefully)
: that the languages the author places higher are most commonly used in
: different application domains than Forth is. One thing that I see
: over and over in this newsgroup is the hidden assumption that everyone
: in the world has the same set of priorities as embedded systems
: programmers. Once you rise up over that assumption, you're likely to
: at least see where the author's conclusions come from.
That's pretty obvious, I think: the language with the greatest feature
set wins. This isn't a sensible way to choose a car, and it isn't a
sensible way to choose a programming language. The author more or
less admits that he's interested in languages for one person which
are suitable for programs which can be quickly thrown together.
There's nothing wrong with that, but it would be unwise to make any
general conclusions from such a study.
Andrew.
Andrew Haley
: Java was (originally) designed for use in embedded applications. It
: only found its true niche on the web, because Java was inherently
: horrible for embedded work.
"Inherently horrible?" From what I can see, Java has many of the
desirable qualities needed in an embedded programmming language. It's
not for small 8 and 16 bit systems, but it was never intended to be.
Andrew.
Wil Baden
> The author more or less admits that he's interested in
> languages for one person which are suitable for programs
> which can be quickly thrown together.
Interesting. That's why I use Forth.
In a typical day I write and use dozens of programs, and throw them
away -- use them and lose them.
Bernd Paysan
> I'm sure that there are microprocessors where there's no point in
> moving strings around in chunks of greater than one byte, but I can't
> say I've ever programmed one. 6502, perhaps? I've programmed one of
> those, but it was a very long time ago.
All 8 bit processors should gain from unrolling a string move, so moving
junks around should be cheaper than looking for termination. I'm not
sure about where 6502 or 8051 show a gain, since I programmed neither.
On PIC, the check for zero certainly is more expensive. But I doubt that
many of these embedded processors really do much string processing.
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/
Bernd Paysan
Anton Ertl wrote:
> > Feature Max Score Comments
>
> > First-Class-Functions 100 0
>
> You can take execution tokens (xts) of words, pass them around or
> store them in any way, and finally EXECUTE or COPMPILE, them. They
> are at least as powerful as C function pointers (C got 20 points in
> this area).
According to the criteria, Forth should get 100 points. It is even
possible to do anonymous lambda function in many Forth systems with a
bit of non-standard work. The following should work in many systems
(change your LAST to whatever you name it).
: :[ ( compile-time: -- orig colon-sys )
last @ POSTPONE AHEAD :noname ; immediate
: ]: ( compile-time: orig colon-sys -- ; run-time: -- xt )
POSTPONE ; >r ] POSTPONE THEN r> POSTPONE ALiteral last !
; immediate
> > Aggregates 200 10
> > 10 points for the very cool CREATE DOES> construct.
>
> It's mostly build-your-own using address arithmethic; if you are too
> lazy for that, you can use existing packages, e.g., the structures in
> http://www.complang.tuwien.ac.at/forth/objects/.
And with a bit of extra work you get a complete set of anonymous
literals for all your aggregates, too.
> > Separate-Compilation 200 0
>
> You can structure programs into several files (using INCLUDED),
> without undue overhead; there is no standard way of path searching,
> however.
I think this is N/A for Forth. You want separate compilation if you have
a slow compiler. The Forth compiler is faster than the C linker (at
least for the Forth systems I wrote ;-), so it really bogs down to being
able to structure your source into different files. Yes, Forth has that.
Ok, every Forth system has it's own path searching, so there's no
standard for that.
> > Objects 100 0
>
> Also build-your-own. And there are lots of them, starting at 12 lines
> (http://www.jwdt.com/~paysan/screenful.html).
Since there are at least 20 different object systems, this scores to at
least 1000 (when one takes into account that perhaps the average OO
extension scores at 50 ;-).
I also completely disagree with Keith on the typing part, especially
when taking the experiences of VHDL and Verilog into account. Verilog is
by all standards an untyped language, as it has only one significant
type, the array of bits (all other types are not used in synthesis).
VHDL has a payload of types, and encourages the user to create more of
those, while insisting that all types are kept separate. Everyone I know
can write correct Verilog modules say in an hour, but to convert those
to type-correct VHDL, it can take days ;-). Just try to assign an
aggregate to a bit-vector (it's illegal!), yet everybody, even those who
don't come from Verilog, fall into that pit.
Worse yet, strong typing distracts you from the real bugs in your
program. If you finally managed to compile your code after endless hours
of inserting casts and writing conversion functions that bogs down to
nothing, you don't see the bugs anymore.
Strong typing IMHO is like the support wheels on a children's bike. They
prevent falling on the side when you stand (low risk operation mode),
but they'll efficiently turn you to the ground when you turn at fast
speed (high risk operation mode). You only have to learn how to ride
without support wheels once, and then you'll never want them back.
Mary Murphy and Leo Wong
>In article <wilbadenF...@netcom.com>,
> wilb...@netcom.com (Wil Baden) wrote:
>> he...@albany.net wrote:
>>
>> > mintest 1648 milleseconds
>> > maxtest 6352 milleseconds
>>
>> Your results look strange. Try them again. If they
>> come out similarly, check with Rick.
>>
>
At home (Cyrix 150):
mintest 2788 milliseconds
maxtest 15915 milliseconds
SwiftForth 1.50.4
Mary Murphy and Leo Wong
benchmark. I ended up right number of B's (1,301) but a smaller
output file. His input file has quite a few duplicate lines. In his
output file, a B can have the same A more than once. In mine it
doesn't. Anyway, my first draft ran in 1537 milliseconds (Cyrix 150).
I think (haven't verified yet) that all his and my B's match up.
By the way the output lines can be very long. In Waclena's file the
longest line is 20,858 characters, in mine 20,101 characters.
So this is Unix?
Bruce McFarling
Ertl) wrote:
>In article <UPK23.208$H5....@newsr1.twcny.rr.com>,
> "John Passaniti" <jp...@rochester.rr.com> writes:
>> Say I merely
>> want to copy a string (usually the most common operation in many
>> programs that manipulate strings). Both ASCIIZ and counted strings
>> will result in code that is equally efficient.
>In a later posting you restrict this to a certain class of processors:
>non-pipelined 8-bit processors (and I doubt that these do a lot of
>string processing nowadays). You should have done so earlier.
That should be non-pipelined 8-bit processors without
dedicated block move instructions. Counted block moves in either
direction are clearly superior on the 65816, because the block move
instruction has much the same effect as an instruction cache would do:
once it gets going, the memory accesses for instruction reads are
eliminated--since its a single instruction that does the block move
itself.
(
----------
Virtually,
Bruce McFarling, Newcastle,
ec...@cc.newcastle.edu.au
)
Andrew Haley
: Andrew Haley <a...@cygnus.remove.co.uk> wrote in message
: news:7j0tau$jqu$1...@korai.cygnus.co.uk...
: > John Passaniti (jp...@rochester.rr.com) wrote:
: > : Sure, for those processors that can address more than a
: > : byte at a time. Let's not forget that many embedded systems
: > : programmers are still pumping out code for 8-bit micros. Hell,
: > : I read that there are more 8051's running code on the planet
: > : than any other microprocessor.
: >
: > Right, but even on an 8051 it's faster to move strings around in
: > chunks of more than one byte at a time.
: Please detail the 8051 instructions which are used to move more than
: one byte at a time. Unless you are talking about a weird derivative,
: the straight 8051 instruction set only deals with byte-wide data
: movements.
Well, lemme see. It's been 10 years since I programmed one, but this
one moves up to 256 bytes, on byte at a time, when the source
addresses and the count are even:
BEGIN
DPTR ) A MOVX A R0 ) MOVX R0 INC DPTR INC
DPTR ) A MOVX A R0 ) MOVX R0 INC DPTR INC
R0 A MOV 0= IF P2 INC THEN
R1 DEC R1 A MOV
0= UNTIL
I haven't an 8051 manual handy, and it's been a long time.
Andrew.
John Passaniti
> : > Right, but even on an 8051 it's faster to move strings around in
> : > chunks of more than one byte at a time.
>
> : Please detail the 8051 instructions which are used to move more
than
> : one byte at a time. Unless you are talking about a weird
derivative,
> : the straight 8051 instruction set only deals with byte-wide data
> : movements.
>
> Well, lemme see. It's been 10 years since I programmed one, but
this
> one moves up to 256 bytes, on byte at a time, when the source
> addresses and the count are even:
All you have done is unroll a loop to move two bytes between each
comparison. The processor itself is still limited to data movements
of eight bits at a time. Your technique is fine if you are going to
start putting preconditions on the strings one might move (souce
address even, count is even), but since we were discussing counted
verses null-terminated strings, you're addressing a different
question.
Jonah Thomas
>All you have done is unroll a loop to move two bytes between each
>comparison. The processor itself is still limited to data movements
>of eight bits at a time. Your technique is fine if you are going to
>start putting preconditions on the strings one might move (souce
>address even, count is even), but since we were discussing counted
>verses null-terminated strings, you're addressing a different
>question.
If speed was more important than memory, for some applications he
could start each string on an even address, and add a nul character
to each odd-length string. That doesn't work for half the possible
substrings but it would work for some applications.
You could start nul-terminated strings on even addresses too, and
you could probably do something about odd lengths. How much slower
would it be? Would it be a trivial difference?
Mary Murphy and Leo Wong
Leo Wong) wrote:
>Not having Wil's tools, I did my own version of Waclena's invert
>benchmark. I ended up right number of B's (1,301) but a smaller
>output file. His input file has quite a few duplicate lines. In his
>output file, a B can have the same A more than once. In mine it
>doesn't. Anyway, my first draft ran in 1537 milliseconds (Cyrix 150).
>
Second draft reproduces Waclena's output exactly. 1800+-400
milliseconds on my Cyrix 150. Third draft used a large (30K) output
buffer, which reduced the time by only about 25%.
Thanks to Wil Baden for his version and e-mail assistance.
\ Invert2.f produces v2.txt = validation.htm
\ After Waclena
\ Fools
1 CELLS CONSTANT CELL
: place ( ca1 u ca2 -- )
2DUP 2>R CHAR+ SWAP CHARS MOVE 2R> C! ;
: string, ( ca1 u ca2 -- )
HERE OVER 1+ CHARS ALLOT PLACE ;
: scan ( ca1 u1 char -- ca2 u2 )
>R BEGIN DUP WHILE OVER C@ R@ <> WHILE 1 /STRING REPEAT THEN
R> DROP ;
\ Binary tree words
CREATE URLs 0 ,
4 CELLS CONSTANT twig \ *string, left, right, filenames
: left ( a1 -- a2 ) CELL+ ;
: right ( a1 -- a2 ) 2 CELLS + ;
: filenames ( a1 -- a2 ) 3 CELLS + ;
: new-twig ( node a u -- anode )
2>R ALIGN HERE TUCK
twig + , 0 , 0 , 0 , ! HERE CELL -
2R> string, ;
\ Linked-list word
: new-node ( struct a u -- )
2>R DUP
BEGIN NIP DUP @ DUP WHILE
DUP CELL+ COUNT 2R@ COMPARE 0> UNTIL THEN
ALIGN HERE SWAP , SWAP ! 2R> string, ;
\ New twig if new URL
: ?twig ( node a u -- )
2>R DUP @
0= IF 2R@ new-twig ROT ROT new-node ELSE
@ DUP @ COUNT 2R@ COMPARE
?DUP 0= IF filenames ROT ROT new-node ELSE
0< IF right ELSE left THEN 2R@ RECURSE
THEN THEN 2R> 2DROP ;
0 VALUE fid
9 CONSTANT Tabchar
CREATE tabpad Tabchar C, ALIGN
\ Split a line a the tab character
: a|b ( a u -- a1 u1 a2 u2 )
2DUP Tabchar SCAN TUCK 2>R - 2R> 1 /STRING ;
\ File input words
: open-in ( -- )
S" input.html" R/O OPEN-FILE THROW TO fid ;
: close-in ( -- )
fid CLOSE-FILE THROW ;
255 CONSTANT maxin \ Increase to suit
CREATE lpad maxin CHARS ALLOT
: read-in ( -- )
BEGIN lpad DUP maxin fid READ-LINE THROW
WHILE a|b URLs ROT ROT ?twig REPEAT 2DROP ;
\ File output words
\ Line format: URL<tab>filename...<tab>filename
\ Write a filename preceded by a tabchar
: write-filename ( node -- )
tabpad 1 fid WRITE-FILE THROW
COUNT fid WRITE-FILE THROW ;
\ Write atwigs
: write-filenames ( filenames -- )
BEGIN @ DUP WHILE DUP CELL+ write-filename REPEAT DROP ;
\ Write a URL and the files it is in
: write-URL ( url -- )
DUP @ COUNT fid WRITE-FILE THROW
filenames write-filenames
PAD 0 fid WRITE-LINE THROW ;
\ Write URLs
: write-URLs ( urls -- )
@ ?DUP
IF DUP left RECURSE
DUP write-URL
right RECURSE
THEN ;
: write-out ( -- )
S" v2.txt" R/W CREATE-FILE THROW TO fid
URLs write-URLs
fid CLOSE-FILE THROW ;
\ COUNTER and TIMER are SwiftForth timing words
COUNTER open-in read-in close-in write-out TIMER
Bruce R. McFarling
wrote:
>Andrew Haley wrote:
>> I'm sure that there are microprocessors where there's no point in
>> moving strings around in chunks of greater than one byte, but I can't
>> say I've ever programmed one. 6502, perhaps? I've programmed one of
>> those, but it was a very long time ago.
>
>All 8 bit processors should gain from unrolling a string move, so moving
>junks around should be cheaper than looking for termination. I'm not
>sure about where 6502 or 8051 show a gain, since I programmed neither.
>On PIC, the check for zero certainly is more expensive. But I doubt that
>many of these embedded processors really do much string processing.
The 65C02 starts gaining once the block of memory to move begins to be
bigger than a page. A page move can be unrolled, because you know
that the check for the Y-index overflow will only happen on a power of
two:
inc count+1
dec count+1
beq +
ldy #0
- lda (source),y
sta (target),y
iny
lda (source),y
sta (target),y
iny
bne -
...
saves 2*(256/2) = 256 cycles per complete page. With this, the tip
over from zero delimited to counted occurs at more than one page. I
think that the general savings is probably (n-1)*(256/n)*p for
n={1,2,4,...256} and p=int(length/256).
However, if there is a class of moves which you know will be less than
a page, and counting does not let you omit string moves, then you
would still be better off with Zstrings for that class of string
moves.
Andrew Haley
: All you have done is unroll a loop to move two bytes between each
: comparison.
Correct.
: The processor itself is still limited to data movements of eight
: bits at a time. Your technique is fine if you are going to start
: putting preconditions on the strings one might move (souce address
: even, count is even), but since we were discussing counted verses
: null-terminated strings, you're addressing a different question.
No. There must be additional code around the loop in question for the
prologue and epilogue, but I have no intention of writing it now.
However, it should be obvious that a precondition of an efficient
unrolled memory copy is knowing how long the string is in advance.
Andrew.
he...@albany.net
he...@albany.net (Mary Murphy and Leo Wong) wrote:
> On Sat, 05 Jun 1999 20:50:27 GMT, he...@albany.net (Mary Murphy and
> Leo Wong) wrote:
> Second draft reproduces Waclena's output exactly. 1800+-400
> milliseconds on my Cyrix 150. Third draft used a large (30K) output
> buffer, which reduced the time by only about 25%.
>
At work version 2 was slower (2870 milliseconds) while version 3
was faster about the same (1220 milliseconds) as at home. My
timings are apparently not generalizable.
For those interested in trying these on their own machines I give
version 3. The input and output can be gotten from:
http://enki.lib.uchicago.edu/keith/crisis/benchmarks/invert/
\ Invert3.f - produces v3.txt = validate.html
\ Uses large output buffer
\ After Waclena
\ http://enki.lib.uchicago.edu/keith/crisis/benchmarks/invert/
\ Fools
1 CELLS CONSTANT CELL
9 CONSTANT Tabchar
: place ( ca1 u ca2 -- )
2DUP 2>R CHAR+ SWAP CHARS MOVE 2R> C! ;
: string, ( ca1 u ca2 -- )
HERE OVER 1+ CHARS ALLOT place ;
: scan ( ca1 u1 char -- ca2 u2 )
>R BEGIN DUP WHILE OVER C@ R@ <> WHILE 1 /STRING REPEAT THEN
R> DROP ;
: k* 10 LSHIFT ;
: @+ DUP CELL+ SWAP @ ;
: ls+! ( a u ls -- )
>R TUCK R@ @+ CHARS + SWAP CHARS MOVE R> +! ;
\ Binary tree words
CREATE URLs 0 ,
4 CELLS CONSTANT twig \ *string, left, right, filenames
: left ( a1 -- a2 ) CELL+ ;
: right ( a1 -- a2 ) 2 CELLS + ;
: filenames ( a1 -- a2 ) 3 CELLS + ;
: new-twig ( node a u -- anode )
2>R ALIGN HERE TUCK
twig + , 0 , 0 , 0 , ! HERE CELL -
2R> string, ;
\ Linked list word
: new-node ( struct a u -- )
2>R DUP
BEGIN NIP DUP @ DUP WHILE
DUP CELL+ COUNT 2R@ COMPARE 0> UNTIL THEN
ALIGN HERE SWAP , SWAP ! 2R> string, ;
\ New twig if new URL
: ?twig ( node a u -- )
2>R DUP @
0= IF 2R@ new-twig ROT ROT new-node ELSE
@ DUP @ COUNT 2R@ COMPARE
?DUP 0= IF filenames ROT ROT new-node ELSE
0< IF right ELSE left THEN 2R@ RECURSE
THEN THEN 2R> 2DROP ;
\ Input/output words
0 VALUE fid
CREATE tabpad Tabchar C,
\ Input words
: a|b ( a u -- a1 u1 a2 u2 )
2DUP Tabchar SCAN TUCK 2>R - 2R> 1 /STRING ;
: open-in ( -- )
S" input.html" R/O OPEN-FILE THROW TO fid ;
: close-in ( -- )
fid CLOSE-FILE THROW ;
255 CONSTANT maxin \ Increase to suit
CREATE lpad maxin CHARS ALLOT
: read-in ( -- )
BEGIN lpad DUP maxin fid READ-LINE THROW
WHILE a|b URLs ROT ROT ?twig REPEAT 2DROP ;
\ Output words
CREATE outpad CELL 24 k* CHARS + ALLOT \ Adjust to suit
\ Write a filename preceded by a tabchar
: write-filename ( node+ -- )
tabpad 1 outpad ls+!
COUNT outpad ls+! ;
\ Write atwigs
: write-filenames ( filenames -- )
BEGIN @ DUP WHILE DUP CELL+ write-filename REPEAT DROP ;
\ Write a URL and the files it is in
: write-URL ( url -- )
0 outpad !
DUP @ COUNT outpad ls+!
filenames write-filenames
outpad @+ fid WRITE-LINE THROW ;
\ Write URLs
: write-URLs ( urls -- )
@ ?DUP
IF DUP left RECURSE
DUP write-URL
right RECURSE
THEN ;
: write-out ( -- )
S" v3.txt" R/W CREATE-FILE THROW TO fid
URLs write-URLs
fid CLOSE-FILE THROW ;
\ COUNTER and TIMER are SwiftForth timing words
COUNTER open-in read-in close-in write-out TIMER
--
he...@albany.net
>
> >> > mintest 1648 milleseconds
> >> > maxtest 6352 milleseconds
>
>
> mintest 2788 milliseconds
> maxtest 15915 milliseconds
>
At work again:
mintest 1620 milliseconds
maxtest 6620 milliseconds
fgrep2 179 milliseconds
So, Rick, why do mintest and maxtest differ on my and
Marcel's machines but not on Wil's?
Wil Baden
( should be CODE definitions eliminating stack manipulation. )
: CMOVE ( src dest len -- )
0MAX
DUP CELL 1- AND IF \ CMOVE
BOUNDS ?DO DUP C@ I C! 1- LOOP DROP
ELSE \ CELL-MOVE
BOUNDS ?DO DUP @ I ! CELL+ CELL +LOOP DROP
THEN ;
: CMOVE> ( src dest len -- )
DUP 0> NOT IF 3DROP EXIT THEN
DUP CELL 1- AND IF \ CMOVE>
1- 2>R R@ + 2R> OVER + DO DUP C@ I C! 1- -1 +LOOP DROP
ELSE \ CELL-MOVE>
CELL- 2>R R@ + 2R> OVER + DO DUP @ I ! CELL- -CELL +LOOP DROP
THEN ;
: MOVE ( src dest len -- )
THIRD OVER U< IF CMOVE> ELSE CMOVE THEN ;
( THIRD is 2 PICK in a single CODE definition. )
( If cell-addresses must be aligned then DUP CELL 1- AND should be
( THIRD THIRD OR OVER OR CELL 1- AND )
( I have also done this with the tests all in MOVE using
( CMOVE CELL-MOVE CMOVE> CELL-MOVE> )
( It lets me switch a 256-character code table in 1 microsecond
( rather than almost 4 microseconds. )
( Common Usage Dependency:
( 1 CHARS is an address unit; 2's Complement Arithmetic;
( Power of 2 cell-size. )
Andrew McKewan
>( The following has been good enough for me so far. CMOVE and CMOVE>
>( should be CODE definitions eliminating stack manipulation. )
>
>: CMOVE ( src dest len -- )
> 0MAX
> DUP CELL 1- AND IF \ CMOVE
> BOUNDS ?DO DUP C@ I C! 1- LOOP DROP
Shouldn't this be 1+ ?
Andrew
Wil Baden
Yes.
(Thanks for catching my finger fumble.)
Anton Ertl
"Marcel Hendrix" <m.a.m....@ele.tue.nl> writes:
> he...@albany.net wrote in message <7j3u46$qm0$1...@nnrp1.deja.com>...
> >1. Is there a reason why the programmer wanted a 20 K buffer
> > to test his benchmark?
A cheap, but unreliable way of dealing with long lines.
> This would depend on the implementation of READ-LINE. Under DOS, NT
> and Linux I have not had much luck in finding system calls for unbuffered
> reads of {cr lf} delimited lines. Therefore I suspect that in general a
> Forth will attempt to read as many bytes as READ-LINE's user specifies
> and then simply throws away what's not needed. Thus it is not wise to
> specify excessively long lines.
You mean, the time READ-LINE uses will be proportional to the length
of the buffer, not to the length of the read line?
If yes, that's perverse. I would want my money back from anyone who
sold me such a Forth system.
> Finally, the READ-LINE arguments suggest there is no hidden buffering going
> on and the user should optimize the size himself.
I don't see any trace of this in the standard.
> >2. Would a larger than necessary buffer slow down (speed up?)
> > READ-LINE or does the size of the buffer not matter?
If anything, a larger buffer should produce a speedup in those cases,
where a shorter buffer requires processing the line in several
batches. A larger buffer certainly should not slow down READ-LINE in
a serious implementation.
- anton
--
M. Anton Ertl Some things have to be seen to be believed
an...@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html
Anton Ertl
he...@gmx.net (Helge Horch) writes:
> an...@mips.complang.tuwien.ac.at (Anton Ertl) wrote:
> >The way you do macros in Forth is
> >with IMMEDIATE, POSTPONE and LITERAL. You can use the full power of
> >the language in macro definitions, so IMO the rating is well-deserved.
>
> I'd second the rating, but I have also added Wil's MACRO (which uses
> EVALUATE) to my tool set.
If you are happy with Perl-like unreliability, EVALUATE is fine.
Otherwise, read
http://www.complang.tuwien.ac.at/forth/why-evaluate-is-bad on the
problems of using EVALUATE and how to use it safely (short version:
"Don't!").
Anton Ertl
"John Passaniti" <jp...@rochester.rr.com> writes:
> All you have done is unroll a loop to move two bytes between each
> of eight bits at a time. Your technique is fine if you are going to
> start putting preconditions on the strings one might move (souce
> address even, count is even), but since we were discussing counted
> verses null-terminated strings, you're addressing a different
> question.
With addr u strings it's quite easy to adjust the start condition:
just test for oddness and possibly move one byte, then you can do the
rest with the optimized routine. No such luck with the zero-terminated
string.
Wil Baden
I think that what Anton -- one of the few computer scientists
among us -- writes is worth a lot.
However his arguments against macros do not convince me.
I have looked over my uses of macros, and in every one I want
it to be an abbreviation of text.
The components of a macro are virtually always unambiguous,
and if they are changed, I want the change to be used.
(
--
Wil Baden Costa Mesa, California WilB...@Netcom.com
)
P.S. I can think of one macro that does have ambiguous
components.
TRAVERSE foo
yields
foo REWIND BEGIN foo READ WHILE
REWIND and READ are different for foo as a FILES object,
a LINKED-LIST object, and none of the above.
The ambiguity is in the text, not the macro.
I definitely want TRAVERSE foo to be an abbreviation
of the text.
--
W.
Marcel Hendrix
> In article <375b1a87...@news.albany.net>,
> he...@albany.net (Mary Murphy and Leo Wong) wrote:
>> On Sat, 05 Jun 1999 20:50:27 GMT, he...@albany.net (Mary Murphy and
>> Leo Wong) wrote:
>> Second draft reproduces Waclena's output exactly. 1800+-400
>> milliseconds on my Cyrix 150. Third draft used a large (30K) output
>> buffer, which reduced the time by only about 25%.
> At work version 2 was slower (2870 milliseconds) while version 3
> was faster about the same (1220 milliseconds) as at home. My
> timings are apparently not generalizable.
With iForth your code runs in 1018 +/- 20 ms. Apparently this benchmark
is completely I/O-bound and neither of us have invested in extremely
fast harddisks.
I tried to rewrite the code (tail recursion can be removed almost
everywhere) but it only brings 50 to 80 ms extra speed (950 +/- 5ms).
Another indicator of being hardware I/O-bound.
-marcel
Mary Murphy and Leo Wong
Ertl) wrote:
[interesting stuff]
So how does GForth perform on mintest maxtest and Waclena's other
benchmarks?
Mary Murphy and Leo Wong
>
>So, Rick, why do mintest and maxtest differ on my and
>Marcel's machines but not on Wil's?
This I found interesting (SwiftForth):
mintest
zygote
3453 milliseconds ok
lpad 36 DUMP
4570D8 7A 79 67 6F 74 65 0D 0A 7A 20 20 20 20 20 20 20 zygote..z
4570E8 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
4570F8 20 20 20 20
ok
maxtest
zygote
21051 milliseconds ok
lpad 36 DUMP
4570D8 7A 79 67 6F 74 65 0D 0A 7A 79 67 6F 74 65 0D 0A
zygote..zygote..
4570E8 7A 79 67 6F 74 65 0D 0A 7A 79 67 6F 74 65 0D 0A
zygote..zygote..
4570F8 7A 79 67 6F zygo
ok
Sorry for bad formatting.
Anton Ertl
My arguments are not against macros, but against the use of EVALUATE
(except under special circumstances). Macros defined using POSTPONE,
LITERAL, and COMPILE, are fine.
> do not convince me.
I know.
> I have looked over my uses of macros, and in every one I want
> it to be an abbreviation of text.
So a macro is not an abstraction for you, it's meaning has to be
determined through examining all the text that it expands to, right?
> The components of a macro are virtually always unambiguous,
A collegue told me that "virtually" is a synonym for "not".
That's also the problem with Perl: Perl programs virtually always
work. Many people are content with that state of things, and they
like and use Perl; these people will probably also find EVALUATE-based
macros acceptable.
I don't. I want my programs to really work, and if the effort is as
small as using POSTPONE instead of EVALUATE and avoiding Perl, I take
it.
> and if they are changed, I want the change to be used.
But why only changes between macro definition and macro use time? Why
not later changes (i.e., every change before run-time)? Why not write
every colon def like this:
: foo s" bar flip flop" evaluate ;
(I am sure you can make up a macro that makes the syntax look nicer,
as can I).
This would give you the ultimate in using changes, just like
Postscript.
William Tanksley
> wilb...@netcom.com (Wil Baden) writes:
>> However his arguments against macros
>My arguments are not against macros, but against the use of EVALUATE
>(except under special circumstances). Macros defined using POSTPONE,
>LITERAL, and COMPILE, are fine.
>> I have looked over my uses of macros, and in every one I want
>> it to be an abbreviation of text.
>So a macro is not an abstraction for you, it's meaning has to be
>determined through examining all the text that it expands to, right?
It's an abstraction; it's just not the same abstraction as POSTPONE.
>> and if they are changed, I want the change to be used.
>But why only changes between macro definition and macro use time? Why
>not later changes (i.e., every change before run-time)? Why not write
>every colon def like this:
Because of the hierarchy of design: we want to decide things never if
possible, then at design-time, then compile-time, and if none of those
work, then at runtime. (Source: Chuck Moore, with one addition by me.)
Explanation of the first level ("never if possible"): the most reliable
part of any program is that part that isn't there. It never breaks,
always meets specifications, and never requires any mistaken debugging
energy. Therefore, make your programs simple and limited in focus. This
is making your decision at never-time, as opposed to compile-time or
run-time. (Source: Jon Bentley, "Programming Pearls", my paraphrase of
his quote of someone else.)
Text macros make the decision a little bit later in the process, so
they're less recommended than postpone-macros. Nonetheless, both are
essentially compile-time, and so both are better than any runtime
solution.
>- anton
--
-William "Billy" Tanksley
Utinam logica falsa tuam philosophiam totam suffodiant!
:-: May faulty logic undermine your entire philosophy!
Wil Baden
> A collegue told me that "virtually" is a synonym for "not".
That's how I use it. It amuses me to do it, but I see that others
don't get the joke.
John Passaniti
Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote in message
news:7jjf5s$slh$1...@news.tuwien.ac.at...
> A collegue told me that "virtually" is a synonym for "not".
>
> That's also the problem with Perl: Perl programs virtually
> always work. Many people are content with that state of
> things, and they like and use Perl; these people will probably
> also find EVALUATE-based macros acceptable.
I can understand your comments about EVALUATE, and I can see how they
apply to Perl. But the sentence "Perl programs virtually always work"
is confusing. Are you saying that the set of Perl programs that use
eval "virtually" always work (which I can agree with, given the
dangers of eval), or are you making a larger statement about all Perl
programs?
If your statement is the latter, how can you justify that statement?
William Tanksley
>>its design goals and target market. Just as folks today are encountering
>>much frustration attempting to use Java (designed for whizzy internet
>>graphics on big workstations) in embedded systems, it shouldn't surprise
>Actually, no -- Java was (originally) designed for use in embedded
>applications. It only found its true niche on the web, because Java was
>inherently horrible for embedded work.
Bytecodes do have advantages for embedded work of the sort for which Java
is intended. They use less memory than anything aside from a native
solution.
And for the Web, most people aren't using Java for that anymore. Java
_is_ nice for distributed apps, but applets seem to be just a pain.
Bytecodes are certainly non-optimal for this type of work, because memory
is not at a premium. Semantic Trees would have been better.
> KC5TJA/6 | -| TEAM DOLPHIN |-
Bruce R. McFarling
Ertl) wrote:
>In article <wilbadenF...@netcom.com>,
> wilb...@netcom.com (Wil Baden) writes:
>> The components of a macro are virtually always unambiguous,
>A collegue told me that "virtually" is a synonym for "not".
Whether or not in general, "virtually always" and "not always" are
obviously identical in meaning, only differing in spin.
Andrew Haley
: On Fri, 04 Jun 1999 23:23:19 GMT, Samuel A. Falvo II wrote:
: >>its design goals and target market. Just as folks today are encountering
: >>much frustration attempting to use Java (designed for whizzy internet
: >>graphics on big workstations) in embedded systems, it shouldn't surprise
: >Actually, no -- Java was (originally) designed for use in embedded
: >applications. It only found its true niche on the web, because Java was
: >inherently horrible for embedded work.
: Bytecodes do have advantages for embedded work of the sort for which Java
: is intended. They use less memory than anything aside from a native
: solution.
It's more useful to think about the Java programming language and the
Java VM as two separate things.
The Java VM is a target for many several programming languages: Java
itself, Scheme, Ada, and several others. It's very useful for this,
as it presents a portable and fairly efficient target platform for
compiler development.
Java itself is "just" another programming language: there is no
requirement that Java programs compile to bytecode. The Java
programming language may be compiled to code for the Java VM or to
native code via gcj, or even code for some other VM.
: And for the Web, most people aren't using Java for that anymore.
: Java _is_ nice for distributed apps, but applets seem to be just a
: pain. Bytecodes are certainly non-optimal for this type of work,
: because memory is not at a premium.
Perhaps, but having a single ubiquitous platform as a _lingua franca_
is a tremendous enabler, even if that platform isn't ideal.
: Semantic Trees would have been better.
Because?
Andrew.
Bart Lateur
>Andrew Haley wrote ...
>> Right, but even on an 8051 it's faster to move strings around in
>> chunks of more than one byte at a time.
>
>Please detail the 8051 instructions which are used to move more than
>one byte at a time.
The same ones (I don't know them by heart). But you can do more than one
byte move within a loop, when you use counted strings. In pseudo-code:
DO
move-a-byte
move-a-byte
move-a-byte
move-a-byte
LOOP
where you move 4 bytes in a loop, for the bulk of the string. Moving the
final odd bytes at the end, isn't optimized (and it needn't be).
You can't use this kind of optimization with ASCIIZ strings.
Bart.
Samuel A. Falvo II
>
>Because?
Because they are often smaller than pure bytecode, they load faster, and are
always natively compiled on the platform executing them. Reference any web
page relating to Juice, for instance, the best known of the semantic
tree-based application distribution formats. I really do need to research
ANDF and XANDF too, now that I think about it.
I plan on supporting some kind of semantic tree loader for Dolphin, my OS.
I just haven't figured out which one yet. :-)
==========================================================================
KC5TJA/6 | -| TEAM DOLPHIN |-
DM13 | Samuel A. Falvo II
QRP-L #1447 | http://www.dolphin.openprojects.net
Oceanside, CA |......................................................
Jean-Francois Brouillet
In article <slrn7lqhlh....@dolphin.openprojects.net>,
wtan...@dolphin.openprojects.net (William Tanksley) wrote:
[...]
> Because of the hierarchy of design: we want to decide things never if
> possible, then at design-time, then compile-time, and if none of those
> work, then at runtime. (Source: Chuck Moore, with one addition by me.)
[...]
How is it that you can make me feel so uneasy in just three lines ?
How is it possible to construct such a nicely put sentence that is,
at the same time, so obviously wrong?
Since I'm not too hot to start a flame war, I'm simply going to ask
you to look-up one word in the English dictionary of your choice:
Dynamism
Once you've grabbed that concept, I challenge you to write another
three lines sentence, that would be Right (TM) this time ;-)
Marcel Hendrix
> On Mon, 07 Jun 1999 14:43:56 GMT, he...@albany.net wrote:
[..]
>This I found interesting (SwiftForth):
> mintest
> zygote
> 3453 milliseconds ok
> lpad 36 DUMP
> 4570D8 7A 79 67 6F 74 65 0D 0A 7A 20 20 20 20 20 20 20 zygote..z
> 4570E8 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
> 4570F8 20 20 20 20
> ok
Well? Please help me understand what's mysterious here? (Apart from
the timing being much worse than your previous ones.)
I don't understand the "z" at offset 8, given the fact that mintest
asks for 8 bytes and there is no line in the file with more than 6
bytes? (Assuming you blanked lpad before mintest.)
> maxtest
> zygote
> 21051 milliseconds ok
> lpad 36 DUMP
> 4570D8 7A 79 67 6F 74 65 0D 0A 7A 79 67 6F 74 65 0D 0A zygote..zygote..
> 4570E8 7A 79 67 6F 74 65 0D 0A 7A 79 67 6F 74 65 0D 0A zygote..zygote..
> 4570F8 7A 79 67 6F zygo
> ok
Evidently SwiftForth reads as many bytes as you requested, and after that
scans for delimiters? It might be efficient, given "infinite resources".
-marcel
Marcel Hendrix
> In article <7j64a2$o...@news.tue.nl>,
> "Marcel Hendrix" <m.a.m....@ele.tue.nl> writes:
>> he...@albany.net wrote in message <7j3u46$qm0$1...@nnrp1.deja.com>...
>> >1. Is there a reason why the programmer wanted a 20 K buffer
>> > to test his benchmark?
> A cheap, but unreliable way of dealing with long lines.
Judging from this thread, a very common approach (Wil Baden claims
to do it right, ie. read long lines using a short buffer, but I didn't
succeed in understanding his code).
>> This would depend on the implementation of READ-LINE. Under DOS, NT
>> and Linux I have not had much luck in finding system calls for unbuffered
>> reads of {cr lf} delimited lines. Therefore I suspect that in general a
>> Forth will attempt to read as many bytes as READ-LINE's user specifies
>> and then simply throws away what's not needed. Thus it is not wise to
>> specify excessively long lines.
> You mean, the time READ-LINE uses will be proportional to the length
> of the buffer, not to the length of the read line?
No, this does not logically follow from my hypothesis. For your
corollary to be true there should additionally be a proportional
time difference between reading say 10 bytes and say 8192 bytes (*)
I don't think this is true for current (or even older) harddisks.
(*) Assuming that the time to scan for delimiters is negligible,
which is certainly true for present Forths.
> If yes, that's perverse. I would want my money back from anyone who
> sold me such a Forth system.
If that's the only problem you can find with it ... :-)
>> Finally, the READ-LINE arguments suggest there is no hidden buffering going
>> on and the user should optimize the size himself.
> I don't see any trace of this in the standard.
Given the stack diagram of READ-LINE , IMHO it is not too far-fetched
to assume that the bytes are read from the disk directly into the user
buffer. Furthermore, what use are the extra two required bytes at the
end of the user buffer if hidden buffering can be assumed. (All this
qualifies as a "trace" in my book, but of course and thank goodness,
there is absolutely no guarantee that it actually will work that way.)
>> >2. Would a larger than necessary buffer slow down (speed up?)
>> > READ-LINE or does the size of the buffer not matter?
> If anything, a larger buffer should produce a speedup in those cases,
> where a shorter buffer requires processing the line in several
> batches. A larger buffer certainly should not slow down READ-LINE in
> a serious implementation.
Although I agree, we have not yet seen *conclusive* evidence of such
serious implementations existing. PFE apparently did not suffer from
the large buffer, and Wil's SwiftForth was OK also. Other SwiftForths,
Win32Forth and iForth seem less lucky. More reports would be interesting,
especially if they mention OS, processor and disk speed.
-marcel