[net.micro.amiga] AmigaDos...

DEC.BANKS@MARLBORO.DEC.COM@caip.RUTGERS.EDU (02/01/86)

From: Dawn Banks <DEC.BANKS@MARLBORO.DEC.COM>

   Perhaps some of my comments on AmigaDOS have been slightly misconstrued.
When I compare AmigaDOS to OS-9, it's as constructive criticism, and not an
announcement that AmigaDOS is no good because "it isn't OS-9".  In any case,
while I think that the Amiga software is pretty worth while, I also think
that some properly placed constructive criticism may help make the product
better in the future.  Certainly, you could probably find as many misfeatures
of OS-9 as exist in AmigaDOS, but overall, I think the Amiga could learn a
few things about multitasking from OS-9.

   To reiterate my favorite feature of OS-9's multitasking:  I think the way
OS-9 handles multiple invokations of a task to cause much less overhead.  On
the 6809 version of OS-9 that I've used, all tasks are compiled as position
independent code (an exceedingly easy thing to do on a 6809), with all "own"
storage pointed to by the "U" register.  Thus, when a program is loaded into
memory, no relocation need be performed, and when the task is started, all
that needs to be done is allocate the storage (which includes the stack), and
point U and S at it (and the direct page register), fixup the internal OS-9
data structures, and start the task.  Another invokation would simply 
allocate another storage area, and use the same code segment.  All of this
happens implicitly, without the programmer needing to make any special 
allowances.  This provides the following features:

* Running multiple copies of something doesn't cost you twice for the code
  segment.

* locking a code segment into memory (by incrementing the use count) achieves 
  precisely the same effect as putting it into RAM: on the Amiga, with the
  exception that when you run it, you aren't carrying around two copies of
  the program in ram, as you would be on the Amiga

* Even if the segment isn't locked, running a second invokation happens a lot
  faster, because nothing needs to be read from disk.  This happens more often
  than you might think, most notably with the OS-9 shell.

* library segments can be shared (as with the Amiga), but nothing special needs
  to be done to declare them as libraries, which can save the programmer some
  time.

What all of this boils down to is that (what I think is) the major failing of
the Amiga is its resource utilization.  Sure a 40 meg hard disk and 8M of
RAM would certainly mask the problem, however, I'm still not sure why I should
be finding myself running out of resources so often on a machine with 512K of
ram and two 880K byte floppies.

But, I still like the Amiga and its operating system A LOT.
   --------

hand@ncsu.UUCP (Steven Hand) (02/04/86)

Dawn Banks writes:

>What all of this boils down to is that (what I think is) the major failing of
>the Amiga is its resource utilization.  Sure a 40 meg hard disk and 8M of
>RAM would certainly mask the problem, however, I'm still not sure why I should
>be finding myself running out of resources so often on a machine with 512K of
>ram and two 880K byte floppies.

I agree.  A few years ago I used a PDP-11/60 with the RSX-11/M OS with 6-7
users and several background tasks, all on 128K MEMORY.  Sure it had a hard
disk and swapped tasks in and out of memory, but it shows what can be done with
a professional OS.  It's time for microcomputer OS's to catch up with what
*was* state-of-the-art years ago.

I think OS-9 would be great for the Amiga, but if you want to write your own
quality OS for the Amiga, much of the work has ALREADY BEEN DONE and can be
found in the book

            Operating System Design: The XINU Approach
            by Douglas Comer (Prentice-Hall)

(XINU stands for "XINU is not UNIX").  This very readable book contains
the *SOURCE CODE* for an entire hierarchically-structured OS with MANY features
like:
       - True multitasking.  Processes don't step on each other or crash
         the system.  The resources of *killed* processes are reclaimed.
         Processes can SHARE CODE.  Uses priorities and Round Robin scheduling.
       - Interprocess communication through two kinds of message passing.
         Ports.  NETWORKING with hooks for remote file sharing, servers,
         and diskless nodes.
       - Interrupt-driven, device-independent I/O.  Device drivers.
         Nice file system with ORDERED DISK SEEKS, pseudo-devices, indexed
         sequential access method.
       - Real-time clock, scheduled waits, semaphores (no busy waits).

The book describes how all the routines work and gives the source code in C.
It is all done in about 5800 lines of C and 650 lines of assembler, and runs
in about 4000 bytes (!).
You can get a MAGTAPE from the publisher with all this and a CROSS DEVELOPMENT
SYSTEM that runs on VAX Berkeley UNIX 4.1 or 4.2.  (Includes C compiler for
LSI-11 microcomputer, linking loader, up/down-loaders, debugger, utilities).
While the book describes an LSI-11 as the target, it mentions that students
have ported XINU to the 68000.  Maybe you can get the source for the 68000
version?

Random thoughts...
Maybe the best things about Amiga's OS (libraries, etc.) can be added to XINU.
Since the book is readily available, this could be a group project.
How about integrating the stuff from the Portable User Interface Library.
Since it is copyright 1984, maybe more has been added to the OS that
  isn't mentioned in the book (CLI, spooler, etc.)
The author is mentioned as working at Bell Labs... Are you on the net? What
  do you think?
Actually there are many other OS's out there, maybe from other university
  projects.

Lastly, this book could help the Commodore OS people make Amiga's OS better...
are you listening?

Disclaimer: I have only read the book, not actually used the OS.

jbs@mit-eddie.UUCP (02/04/86)

In article <2987@ncsu.UUCP> hand@ncsu.UUCP (Steven Hand) writes:
>Dawn Banks writes:
>
>>What all of this boils down to is that (what I think is) the major failing of
>>the Amiga is its resource utilization.  Sure a 40 meg hard disk and 8M of
>>RAM would certainly mask the problem, however, I'm still not sure why I should
>>be finding myself running out of resources so often on a machine with 512K of
>>ram and two 880K byte floppies.
>
>I agree.  A few years ago I used a PDP-11/60 with the RSX-11/M OS with 6-7
>users and several background tasks, all on 128K MEMORY.  Sure it had a hard
>disk and swapped tasks in and out of memory, but it shows what can be done with
>a professional OS.  It's time for microcomputer OS's to catch up with what
>*was* state-of-the-art years ago.
>

I think it is important to note however, that if you were to try this
today, using the most recent version of RSX-11/M+, you will find that:

1) Many additional capibilities and "nicities" have been added.

2) The memory requirements have increased dramatically.

3) The CPU overhead has increased significantly.

4) Those same 6-7 users would find the system resources sufficiently
   depleted to make using the machine an unpleasant experience.  2-3
   users would be much more reasonable.

Don't forget also, that the 11/60 dosn't support graphics, windows, etc.,
etc., etc....

Operating systems involve real trade-offs.  Don't fool yourself into
believing that XINU, at 4K bytes, is the answer to this most complex
problem.

Jeff Siegal - MIT EECS

coatta@utcsri.UUCP (Terry Coatta) (02/05/86)

Although the full source code for XINU is given in the Comer book, it
is of limited use.  Many parts of the system would require a substantial
amount of rewriting.  For instance, the file system that Comer uses is
completely flat, and restricted to a maximum of 26 files.  Any useable
version of XINU would have to have the entire set of file system routines
rewritten.  For the Amiga, there would also be massive amounts of code
required to allow XINU to have a pretty visual interface, since Comer
assumes "tty-like" terminals.  Finally, I might add that XINU is not
what I would refer to as good clean OS design (its alot better than some
real OS code I've seen...) -- the use of interrupts, and system processes
is fairly complex, and needlessly so (just look at the way a Thoth
system deals with interrupts, which more or less just makes them look
like messages delivered by another process).

cg@myrias.UUCP (Chris Gray) (02/05/86)

The 68000 can address +/- 32K from the program pointer (+/- 128 if an index
register is also specified). All constant displacements are either 16 bits
or 8 bits (no 32 bit ones - you have to put them in a register and use
indexing to accomplish that). Thus, position independent code would be
limited to 32K byte chunks. That's just not enough, given the code size
of some programs we would want to run on our 8.5Meg Amigas. Also, the
philosophy of Amigados is to allow scatter loading of programs, which can
successfully load a program even if no single available chunk of memory is
big enough for it. This also makes position independent code impossible.

I haven't delved deeply into libraries, but they strike me as a way to get
essentially the same benefits (shared code). If you want to lock some code
into memory, just use it's library and don't do a 'CloseLibrary' before you
exit - voila! The standard AmigaDos CLI takes essentially no time to load
up since it's mostly (entirely?) in the Kickstart stuff. For most of what I
do (writing programs), it is entirely sufficient.

P.S. If you haven't tried running Wack, give it a try. It'll show you all
sorts of neat things about the system.

		Chris Gray {sask,ubc-vision,ihnp4}!alberta!myrias!cg

breuel@h-sc1.UUCP (thomas breuel) (04/24/86)

A complaint, and two questions:

I have philosophical problems with the AmigaDos file system.
The file system appears to be optimised for finding a named entry
quickly and for making directories small and cheap: the directories
are hashed and do not contain the filenames. This means that for
wildcard expansion and select-file-dialog-box'es, one block has
to be read for each entry in a directory.

An unrelated, but (philosophically) similar problem is the use
of linear, linked blocks for file allocation tables.
It appears that allocation blocks are not buffered, so that for
each seek, Dos has to scan through the whole linked list on disk.
Needless to say that this is dreadfully slow.

The above two problems are compounded by the apparent lack of any
attempts to allocate, say, all allocation blocks on the same track
so that scanning through the allocation list may require many seeks.

Now, even if the above statements are not entirely accurate, the fact
remains that the AmigaDos file structure is, for practical purposes,
too inefficient. It discourages seeks and discourages directory scans.
Instead it gives some (doubtful) savings due to small directory sizes
and simplicity of algorithms for seeks (read lazy programmers ?!).

I'm not writing this purely because I disagree with the file system
structure in some abstract manner, but because for several applications,
this file system is almost unusable (e.g. picking characters out of
a 700k Kanji font file).

It should also be noted that a simple disk cache at the disk driver
level is not necessarily going to improve matters. What is really needed
is a way to instruct Dos to keep the allocation tables for a specific
file in memory.

Ultimately, I find that the current file system should be replaced
with something more UN*X like (with name/inode pairs in directories,
inodes, and links). I'm not saying this because I find the UN*X
file system pleasing to the eye, but because it works, and because
I can do an 'echo *' or 'ls' and don't have to wait for minutes.

So, one question, you have seen already: I need a workaround to access
random parts of a large file quickly. I would greatly prefer not to split
the file up... (and that wouldn't necessarily help anyhow).

The other question is: how are the ROM Kernel and AmigaDos actually
glued together? Where and when is each part of the OS loaded? 
Are there hooks for user file system code (e.g. to implement a remote
file system)? Pointers to the documentation or straight answers
would be appreciated.

						Thomas.

mwm@ucbopal.berkeley.edu (Mike (I'll be mellow when I'm dead) Meyer) (04/27/86)

In article <1076@h-sc1.UUCP> breuel@h-sc1.UUCP (thomas breuel) writes:
>A complaint, and two questions:
>
>I have philosophical problems with the AmigaDos file system.
>The file system appears to be optimised for finding a named entry
>quickly and for making directories small and cheap: the directories
>are hashed and do not contain the filenames. This means that for
>wildcard expansion and select-file-dialog-box'es, one block has
>to be read for each entry in a directory.

True, the AmigaDOS file structure looses on globs. However:

>I can do an 'echo *' or 'ls' and don't have to wait for minutes.

Minutes? How about a couple of seconds/file. That's closer to what I get.
For ~20 files, AmigaDOS runs about half the speed of Unix. But Unix is
running on an RA81 and AmigaDOS is running on a floppy.

If you want to do ls -l (AmigaDOS list), Unix gets extra block reads to get
inodes, but AmigaDOS has the same number of reads as with a dir.

>An unrelated, but (philosophically) similar problem is the use
>of linear, linked blocks for file allocation tables.

I'm not quite sure what you're referring to - the linked list of of data
blocks, or the linked list of blocks with pointers to data blocks. The
second one is what's important, and it resembles Unix, except Unix has a
funky multi-level tree. For files with one or three allocation blocks,
AmigaDOS and Unix both need either one or three disk references. For two
allocation blocks, AmigaDOS needs two disk references, and Unix needs three.
For things beyond three allocation blocks, AmigaDOS needs one reference per
block, and Unix uses three or four (depending on Unix flavor) for all of
them. Of course, some Unixes go to linked lists of lists of allocation
blocks. However, with 1K blocks, any file small enough to fit on a floppy
will fit in two or three blocks.

>It appears that allocation blocks are not buffered, so that for
>each seek, Dos has to scan through the whole linked list on disk.
>Needless to say that this is dreadfully slow.

Yeah - all two or three blocks. Some caching is done, though. At the end of
this article, you'll find a program that times calls to Seek (the
capitalization is correct - I used the AmigaDOS calls, not the stdio calls).
The timings look flat, and suggest that the allocation blocks are cached, to
some degree or another. The trackdisk buffer also shows up. It appears that
doing a seek takes ~30 ticks, at least the second time you look in that area
of the file (and I used a 700K+ file). But play with it yourself.  of
course, seeks *DO* seem somewhat slow. Someone oughta play with it some more
(but I'm not gonna).

Interestingly, the Read after the Seek always runs in zero ticks. This
indicates something wrong - the system shouldn't do any physical IO for a
seek until a Read or Write follows it. Even CP/M-80 got that right (at
least, the BIOSes I wrote did).

>The above two problems are compounded by the apparent lack of any
>attempts to allocate, say, all allocation blocks on the same track
>so that scanning through the allocation list may require many seeks.

Actually, you want something like the 4BSD fast file system - trying to put
blocks at the correct interleave on the same track/cylinder. Since the
allocation blocks aren't used very often in normal use (see 'A Trace-Driven
Analysis of the Unix 4.2 BSD File System' in the 10th SOSP), doing that with
allocation blocks isn't suited to a multi-tasking system. The apparent
caching of the allocation blocks when they are read in is probably optimal.

>Now, even if the above statements are not entirely accurate

Well, it looks to me like the one about seeks is flat wrong. The comment
about doing globbing is true; I still can't figure out why they used
globbing so heavily in the WorkBench.

>the fact
>remains that the AmigaDos file structure is, for practical purposes,
>too inefficient.

I hadn't noticed. But I use deep, narrow trees, so directory searching isn't
murderous for me (the Browser has problems when I try to look at other
peoples disk, with fat trees).

>It discourages seeks and discourages directory scans.
>Instead it gives some (doubtful) savings due to small directory sizes
>and simplicity of algorithms for seeks (read lazy programmers ?!).

Sorry, but the AmigaDOS file system is probably less space effecient that
Unix. You add one block for file header, then put the name and link
information in each block in the file. The savings in the directory are
neglible compared to this.

>I'm not writing this purely because I disagree with the file system
>structure in some abstract manner, but because for several applications,
>this file system is almost unusable (e.g. picking characters out of
>a 700k Kanji font file).

Give me a file system, I'll give you an application for which it's almost
unusable. Doing high-quality DBM kills most systems that grew out of the
Multics OS family.

>It should also be noted that a simple disk cache at the disk driver
>level is not necessarily going to improve matters. What is really needed
>is a way to instruct Dos to keep the allocation tables for a specific
>file in memory.

No, you need a GOOD disk caching system - comparable to 4BSD, and better
than the System V cache. The way AmigaDOS handles (or mishandles) memory
management makes this nontrivial. I hope to take a crack at it sometime this
year.

>Ultimately, I find that the current file system should be replaced
>with something more UN*X like (with name/inode pairs in directories,
>inodes, and links). I'm not saying this because I find the UN*X
>file system pleasing to the eye, but because it works, and because

No, NO, NO! Going to an ilist with name/inode pairs DOUBLES the number of
disk accesses to open a file by name! It also makes the file system less
robust - a hit on the ilist is fatal to Unix, but the AmigaDOS file system
can theoretically be recovered from any single-block hit. The AmigaDOS file
system is theoretically faster than the Unix file system for most
operations, the major exception being searching a directory. It trades space
and links for robustness. On a home machine, this is a win - *IF* there's a
tool for rebuilding broken disks. I understand that MetaComCo has one; why
don't we have it?

>So, one question, you have seen already: I need a workaround to access
>random parts of a large file quickly. I would greatly prefer not to split
>the file up... (and that wouldn't necessarily help anyhow).

I suggest you use the same solution that people who need fast disk access
on Unix used. Use the raw disk. There are examples of using the trackdisk
driver floating around on the net; using that makes doing your seeks easy:
divide the byte number you want by the number of bytes per track, and go
read the track it's on. There's no way to make it go faster, except buying
faster disks.

	<mike
/*
 * seektest - a quick test to see if the time to seek to a byte is
 *	flat, or if it gets longer as you go farther into the file.
 */

#include <exec/types.h>
#include <stdio.h>
#include <libraries/dos.h>

static long	file ;
void		do_seek(int), do_read(int), done(int, char *) ;

void
main(argc, argv) char **argv; {
	struct DateStamp	How_Long, Time_Function() ;
	int			whereto ;

	if (argc < 2) done(20, "usage: seektest <file>") ;
	if ((file = Open(argv[1], MODE_OLDFILE)) == 0)
		done(20, "can't open input file") ;

	for (;;) {
		printf("? ") ;
		scanf("%d\n", &whereto) ;
		if (whereto == 0) done(0, "exit") ;
		Seek(file, 0, OFFSET_BEGINING) ;
		How_Long = Time_Function(do_seek, whereto) ;
		printf("Seek took %5d ticks\n", How_Long . ds_Tick) ;
		How_Long = Time_Function(do_read, 0) ;
		printf("Read took %5d ticks\n", How_Long . ds_Tick) ;
		}
	}
/*
 * Time_Function - just return a DateStamp saying how long it took
 *	to call the given function with the given argument
 */
struct DateStamp
Time_Function(function, argument) void (*function)(int); int argument; {
	struct DateStamp	start, end, diff ;

	DateStamp(&start) ;
	(*function)(argument) ;
	DateStamp(&end) ;

	diff . ds_Tick = end . ds_Tick - start . ds_Tick ;
	if (diff . ds_Tick < 0) {
		diff . ds_Tick += (60 * TICKS_PER_SECOND) ;
		--(end . ds_Minute) ;
		}
	diff . ds_Minute = end . ds_Minute - start . ds_Minute ;
	if (diff . ds_Minute < 0) {
		diff . ds_Minute += (24 * 60) ;
		--(end . ds_Days) ;
		}
	diff . ds_Days = end . ds_Days - start . ds_Days ;
	return diff ;
	}
/*
 * do_seek - seek to where in (global) file.
 */
void
do_seek(where) int where; {
	if (Seek(file, where, OFFSET_BEGINING) < 0)
		done(20, "Seek failed") ;
	}
/*
 * do_read - get one byte from the (global) file, and throw it away.
 */
void
do_read(shit) int shit; {
	int	junk ;
	if (Read(file, &junk, 1) < 0) done(20, "Read failed") ;
	}
/*
 * done - just exit, no problems.
 */
void
done(how, why) int how; char *why; {

	fprintf(stderr, "seektest: %s\n", why) ;
	exit(how) ;
	}

daveh@cbmvax.UUCP (04/29/86)

In article <1076@h-sc1.UUCP> breuel@h-sc1.UUCP (thomas breuel) writes:
>A complaint, and two questions:
>
>I have philosophical problems with the AmigaDos file system.
>The file system appears to be optimised for finding a named entry
>quickly and for making directories small and cheap: the directories
>are hashed and do not contain the filenames. This means that for
>wildcard expansion and select-file-dialog-box'es, one block has
>to be read for each entry in a directory.

Cheap directories are important on a small-disk machine.  And at least this
method allows for essentially unlimited directory sizes, unlike other DOS
systems popular on microcomputers today.

>I'm not writing this purely because I disagree with the file system
>structure in some abstract manner, but because for several applications,
>this file system is almost unusable (e.g. picking characters out of
>a 700k Kanji font file).
>
>It should also be noted that a simple disk cache at the disk driver
>level is not necessarily going to improve matters. What is really needed
>is a way to instruct Dos to keep the allocation tables for a specific
>file in memory.
>
>Ultimately, I find that the current file system should be replaced
>with something more UN*X like (with name/inode pairs in directories,
>inodes, and links). I'm not saying this because I find the UN*X
>file system pleasing to the eye, but because it works, and because
>I can do an 'echo *' or 'ls' and don't have to wait for minutes.

Though, really, when was the last time you hacked on lots of UN*X stuff
on a micro with 3 1/2" floppies.  Most of the VAX or SUN machines would
run even AmigaDOS style directories quite a bit faster.

>So, one question, you have seen already: I need a workaround to access
>random parts of a large file quickly. I would greatly prefer not to split
>the file up... (and that wouldn't necessarily help anyhow).
>
>The other question is: how are the ROM Kernel and AmigaDos actually
>glued together? Where and when is each part of the OS loaded? 
>Are there hooks for user file system code (e.g. to implement a remote
>file system)? Pointers to the documentation or straight answers
>would be appreciated.
>
>						Thomas.

You could directly access below AmigaDOS, which is also the answer to your
last question as well.  The ROM Kernal supports a disk-loaded device, called
"trackdisk.device", as the low-level disk interface.  Going any lower would
put you at in direct contact with the hardware, which is something you 
really don't want.  Anyway, the trackdisk device allows read or write of 
any 512 byte block in the disk, and the RKM gives examples of accessing
this in terms of linear blocks, or in terms of track, sector, and disk
side.  In any case, AmigaDOS builds on top of this, assigning specific
values to certain longwords in every 512 byte block.  The AmigaDOS Technical
Reference Manual (from the developer's kit) is a good pointer to the way
DOS organizes directory, file, and data blocks out on the disk.  Last
weekend I saw a consumer version of this book, called the AmigaDOS Reference
Guide, or something like that, in Walden Books in the Deptford Mall in
NJ.  The book actually contained the developers' AmigaDOS User's Manual,
the Developers' Manual, and the AmigaDOS Technical Reference Guide.  For
a specialized application, its certainly possible to go below the DOS
level, and it might even be reasonable to write your data in a DOS 
compatible format, but where you have control over which blocks get allocated
in which order, to perhaps facilitate faster reading of your files.
-- 

Dave Haynie    {caip,inhp4,allegra,seismo}!cbmvax!daveh
               "There, beyond the bounds of your weak imagination
                Lie the noble towers of my city, bright and gold"
								-Genesis

cc1@ucla-cs.ARPA (Michael Gersten) (04/29/86)

In article <160@cbmvax.cbmvax.cbm.UUCP> daveh@cbmvax.UUCP (Dave Haynie) writes:
>In article <1076@h-sc1.UUCP> breuel@h-sc1.UUCP (thomas breuel) writes:
>>A complaint, and two questions:
>>
>>I have philosophical problems with the AmigaDos file system.
>>The file system appears to be optimised for finding a named entry
>>quickly and for making directories small and cheap: the directories
>>are hashed and do not contain the filenames. This means that for
>>wildcard expansion and select-file-dialog-box'es, one block has
>>to be read for each entry in a directory.
>
>Cheap directories are important on a small-disk machine.  And at least this
>method allows for essentially unlimited directory sizes, unlike other DOS
>systems popular on microcomputers today.
>

*** THOSE ARE NOT CHEAP DIRECTORIES ***
They are VERY expensive. 512 bytes per file entry, plus another 512
for the directory itself. My model 1 (it is NOT trash-dos) needs only 32
bytes per file (plus one for hash byte); it can support directories
with no more space needed.
(But it does, like unix, has only a fixed number of 'inodes' (fde's,
file directory entries. Max of 224. And no, it has no directory support,
but no more space would be needed.)

Now, here's a real question. Take a typical AmigaDos disk, and a typical
Unix file system, and a typical ms-dos disk. Compare the % overhead
on each, where overhead is defined as
  space used   -   data (in bytes)
   ------------------
	space used

and compare. My guess is that Amiga will come out with a high overhead.

disclaimer | ihnp4!ucla-cs!cc1 | Michael Gersten | Joke: 412
-- 
Views expressed here may not be those of the Computer Club, UCLA, or anyone.

breuel@h-sc1.UUCP (thomas breuel) (04/30/86)

Before getting into a closer, point by point discussion (see next
article), let me re-phrase my questions about AmigaDOS:

-- how can I implement a custom file system? Can I write a
   'File Handler Process' (mentioned in the AmigaDOS Technical
   Reference Manual)? Where is this documented in detail?

-- how can I get fast seeks on a file? I don't require blinding
   speed, but delays in the second range for seeks on long files
   are just unacceptable. One solution, albeit a dirty hack, is
   to re-implement the file handler with sufficient buffering
   in my application. Needless to say that I am reluctant to do this.
   The kind of solution I would hope for is that there is a way
   to instruct the file system handler to buffer larger chunks of
   the block allocation table for a particular file.

   The fact that seeks are extremely slow is also (presumably) the
   reason why Manx ln and ALINK are so slow (but this is just a guess).
   If this problem isn't fixed in future releases of the system,
   I predict that there will be problems with getting database
   applications to work at acceptable speeds on the Amiga.

Any help and pointers to the documentation would be appreciated
(i.e. page references in the technical documentation).

						Thomas.

PS: these are by no means my only questions about AmigaDOS, but they
are, at the moment, the most important ones.

jamesp@tekla.UUCP (James Perkins) (04/30/86)

In article <1076@h-sc1.UUCP> breuel@h-sc1.UUCP (thomas breuel) writes:
>A complaint, and two questions:
>
>I have philosophical problems with the AmigaDos file system.
>The file system appears to be optimised for finding a named entry
>quickly and for making directories small and cheap: the directories
>are hashed and do not contain the filenames. This means that for
>
>						Thomas.

Thomas goes on to say we should eventually replace the AmigaDOS file system
with something more UN*X-like.

I do not disagree with you at all, Thomas, but I can think of a
possible quick hack to speed up getting a directory listing from the
shell, or matching wildcards.  This idea comes from a fls 'fast ls'
program on our VAX BSD UN*X system here at work.

I am assuming that AmigaDOS keeps "last modified dates" for each file
and each directory, and that the "last modified date" of the directory
is updated only when the directory contents change.  (DISCLAIMER: I do
not own an AMIGA [yet], nor have I perused the refernce manuals in any
great detail, so I may be speaking completely out of my a**.)

It would require a "get_file_names(matchstring)" routine which expects
to find a 'lsfile' in each directory, which contains all the names of
the files in the directory.  1: If there is no lsfile present in the
directory to be listed, it would build a new one by polling all the
files in the directory for thier filenames.  Then one would 2:  compare
the last modified date of the 'lsfile' to the last modified date of the
directory -- if the directory was newer than the lsfile, a new lsfile
would be generated by getting the filenames out of each file; then
proceed to step 3: the contents of lsfile is a list of all filenames in
the directory -- now get_file_names() searches this list with whatever
pattern(s) you give it, and returns a pointer to some static list of
the filenames found.  This will be slow each time you add or delete
files in each directory, as it has to rebuild the list of filenames,
but relatively fast if the directory contents are static.  This would
make it possible to browse through the directories (oh, what's over
there) instead of dreading each list.

In all reality, of course, this is just a hacked-up logical addition to
the directory structure, and if the filename data were stored IN the
directories, then there would not be a need to maintain a seperate
database of names.  Still, having a "name database" could allow scans
of the directory's contents be MUCH faster, having to only open 2 files
in the optimal case, instead of 20 or 30.

-- 

		 _|_				James T. Perkins
	  __|__ |___| |\     Terror
	  |___|	|___| | \      on the		tektronix!orstcs!jamesp
	  |___| |___| |  \	 high		tektronix!dadla!jamesp
	 _|___| |___| |___\	   seas
	/...\_____|___|____\_/			4635 S.W. Hillside Drive
	\   o o o o o o o  /			Portland, Oregon 97221
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

breuel@h-sc1.UUCP (thomas breuel) (04/30/86)

||I can do an 'echo *' or 'ls' and don't have to wait for minutes.
|
|Minutes? How about a couple of seconds/file. That's closer to what I get.
|For ~20 files, AmigaDOS runs about half the speed of Unix. But Unix is
|running on an RA81 and AmigaDOS is running on a floppy.

It can take quite some time to list all the files in a directory,
into the 60 sec range for some of the disks I have.

||It appears that allocation blocks are not buffered, so that for
||each seek, Dos has to scan through the whole linked list on disk.
||Needless to say that this is dreadfully slow.
|
|Yeah - all two or three blocks. Some caching is done, though. At the end of
|this article, you'll find a program that times calls to Seek (the
|capitalization is correct - I used the AmigaDOS calls, not the stdio calls).
|The timings look flat, and suggest that the allocation blocks are cached, to
|some degree or another. The trackdisk buffer also shows up. It appears that
|doing a seek takes ~30 ticks, at least the second time you look in that area
|of the file (and I used a 700K+ file). But play with it yourself.  of
|course, seeks *DO* seem somewhat slow. Someone oughta play with it some more
|(but I'm not gonna).

Seeking through the two or three linearly linked allocation blocks
on disk can be excrutiatingly slow, however, if you have to do
it for every seek, and if they are scattered. This seems to be the
case for several of my disks. I can assure you that in several cases
I had a strong dependence of seek time on position in the file, i.e.
very fast seeks for the beginning, and long delays for seeks near the
end of the file.

Some arithmetic (correct me if I'm wrong): a file header block
or a file list block contains 72 block pointers, which represent
36k of data in a file. For a 720k file, the allocation table
can therefore grow to 20 blocks. For a search through a linear
chain of blocks, this is not insignificant anymore.

|The comment
|about doing globbing is true; I still can't figure out why they used
|globbing so heavily in the WorkBench.

It's because people like me forget their filenames so often :-).
A very large percentage of my CLI commands are dir's (on UN*X,
ls's). Likewise, most people probably prefer to be shown a dialog
box listing all available files, ready for click selection, to
a string dialog box.

|Sorry, but the AmigaDOS file system is probably less space effecient that
|Unix. You add one block for file header, then put the name and link
|information in each block in the file. The savings in the directory are
|neglible compared to this.

Well, the only savings are that a new, virgin directory costs nothing.
Nothing (other than speed on hashed directory searches) can really
be gained by moving the name from the directory into the inode, since
the amount of information about each file is still the same.

||Ultimately, I find that the current file system should be replaced
||with something more UN*X like (with name/inode pairs in directories,
||inodes, and links). I'm not saying this because I find the UN*X
||file system pleasing to the eye, but because it works, and because
|
|No, NO, NO! Going to an ilist with name/inode pairs DOUBLES the number of
|disk accesses to open a file by name! It also makes the file system less
|robust - a hit on the ilist is fatal to Unix, but the AmigaDOS file system
|can theoretically be recovered from any single-block hit. The AmigaDOS file
|system is theoretically faster than the Unix file system for most
|operations, the major exception being searching a directory. It trades space
|and links for robustness. On a home machine, this is a win - *IF* there's a
|tool for rebuilding broken disks. I understand that MetaComCo has one; why
|don't we have it?

I was not suggesting a file system *identical* to UN*X. But there are
other alternatives. Again, I personally favour the idea of tree-like
allocation tables (because it makes truely random accesses affordable).
Also, it can actually help save space greatly if it allows for small
'seedling' files (just one allocated block) like ProDos.

I believe that the loss of efficiency in 'open' by putting names back
into directories is tolerable. Furthermore, for large directories,
the name/inode-pair directory wins over the hash/bucket-list directory
again. If done carefully, the only thing that is lost in terms of
recoverability is that you may not be able to recover a file's name.
Otherwise, such a file system can be as robust as the current Amiga file
system.

Thanks for replying, and I hope people aren't bored by this
discussion.

						Thomas.

bruceb@amiga.UUCP (Bruce Barrett) (05/05/86)

In article <1082@h-sc1.UUCP> breuel@h-sc1.UUCP (thomas breuel) writes:
>[..]
>-- how can I get fast seeks on a file? [..]
>						Thomas.
>
>PS: these are by no means my only questions about AmigaDOS, but they
>are, at the moment, the most important ones.

The seeks within files larger than 37576 bytes can be very slow, especially
if you use OFSET_BEGINNING.  OFFSET_CURRENT turns out to be much better,
but still not blinding.  This will be greatly improved in the next release.
Hope this helps.
--Bruce Barrett.
--C-A, SW QA

bobp@amiga.UUCP (Robert S. Pariseau) (05/05/86)

V1.2 of the system software (now in testing with developers) fixes a
bug which made random access disk I/O run ridiculously slow.

Sigh.....

peter@baylor.UUCP (Peter da Silva) (05/07/86)

> Cheap directories are important on a small-disk machine.  And at least this
> method allows for essentially unlimited directory sizes, unlike other DOS
> systems popular on microcomputers today.

I don't know of any DOS that doesn't allow unlimited directory sizes, and I
don't understand the advantage of leaving the file name out of the directory,
if that is in fact occurring, since space has to be allocated for it anyway.

I do think that giving each icon a seperate file is a mistake, since it makes
folder displays unbearable slow. Why not do what the Integrated Solutions
system does (more or less) and put all the icons in a folder in a single file
in that directory?
-- 
-- Peter da Silva
-- UUCP: ...!shell!{baylor,graffiti}!peter; MCI: PDASILVA; CIS: 70216,1076

mwm@ucbopal.berkeley.edu (Mike (I'll be mellow when I'm dead) Meyer) (05/07/86)

In article <1084@h-sc1.UUCP> breuel@h-sc1.UUCP (thomas breuel) writes:
>It can take quite some time to list all the files in a directory,
>into the 60 sec range for some of the disks I have.

You must have some LARGE directories. The worst case I can find is fish
disk #13, with 106 files and 6 directories, which takes less than 32
seconds to list. My c: directory (with 49 files) takes less than 12
seconds to list. Assuming that things are linear, I've gotta conclude
that you've got directories with over 200 files in them. Even my junk
directory on Unix isn't that bad (yet).

>Seeking through the two or three linearly linked allocation blocks
>on disk can be excrutiatingly slow, however, if you have to do
>it for every seek, and if they are scattered. This seems to be the
>case for several of my disks. I can assure you that in several cases
>I had a strong dependence of seek time on position in the file, i.e.
>very fast seeks for the beginning, and long delays for seeks near the
>end of the file.

Hmmm. I definitely saw no such correspondence. Seeks after the first
took ~30 ticks no matter where in the 700K+ file they were, the first
seek taking between 1.5 and 2.5 times that long, again seemingly
position independent. I started with a fresh disk, so that there should
be little or no fragmentation of the disk. If you didn't do that, you
might try copying your data base to a freshly formatted disk, and seeing
how long it takes.

>Some arithmetic (correct me if I'm wrong): a file header block
>or a file list block contains 72 block pointers, which represent
>36k of data in a file. For a 720k file, the allocation table
>can therefore grow to 20 blocks. For a search through a linear
>chain of blocks, this is not insignificant anymore.

You're right - I goofed. For some reason, I was thinking of 1K blocks,
so each allocation block gets you 200 pointers for about 200K. Sorry.

>|The comment
>|about doing globbing is true; I still can't figure out why they used
>|globbing so heavily in the WorkBench.
>
>It's because people like me forget their filenames so often :-).
>A very large percentage of my CLI commands are dir's (on UN*X,
>ls's). Likewise, most people probably prefer to be shown a dialog
>box listing all available files, ready for click selection, to
>a string dialog box.

No, that's why *YOU* use globbing so heavily, not why the workbench does
(opening *.info when you open a window). I don't run dir's and/or ls's
all that often - but I use file completion a lot :-).

>I was not suggesting a file system *identical* to UN*X. But there are
>other alternatives. Again, I personally favour the idea of tree-like
>allocation tables (because it makes truely random accesses affordable).
>Also, it can actually help save space greatly if it allows for small
>'seedling' files (just one allocated block) like ProDos.

Tree-like allocation tables can be a good thing. Allowing both shouldn't
be hard; it's got to be easier than the blocks/frags stuff that 4BSD does.
Dynamically switching from a "linked list" of two to a log-tree when you
hit three would probably be a good thing, if you're going to do both
anyway (anyone at C/A listening?).

>I believe that the loss of efficiency in 'open' by putting names back
>into directories is tolerable.

Putting names back in directories would cut the number of file entries per
directory block by a factor of 8. It'd also require a redesign of the file
system from the ground up, as you've gotta throw away the hashing and replace
it by something else - say a linear search of the blocks in the directory,
one block per 9 directory entries (roughly).

>Furthermore, for large directories,
>the name/inode-pair directory wins over the hash/bucket-list directory
>again. If done carefully, the only thing that is lost in terms of
>recoverability is that you may not be able to recover a file's name.
>Otherwise, such a file system can be as robust as the current Amiga file
>system.

Hmmm - I'm beginning to suspect that we're using the same term for different
things. Let me take time out to briefly describe the Unix tree structure, so
that I know we're using the same terminology.

The heart of the Unix directory tree is the ilist. This is a set of blocks
at fixed locations on the file system, usually at the front (front of each
cylinder group for 4BSD). Each inode in the ilist contains *all* information
pertinent to a file - owner, size, status bits, pointers to blocks of data.
A directory is a list of names and inode numbers, the inode number being
the index into the ilist.

Given this, it's obvious that an open looks like a loop that does:

	"search directory for name, and get inode number associated with name"
	"Go get block with that inode in it, so we'll have a list of blocks
		for the next directory"

From this, it's obvious that directories with name/inode pairs in them
take 2 disk accesses per element in the path. AmigaDOS takes 1 disk
access per element in the path (both cases assuming that directories
are "small", and ignoring the the overhead to get the file once you've
find it). Putting names back in the directory will just make the definition
of "small" directories much smaller.

On the other hand, going to name/inode pairs in the directory gets you back
to 2 disk accesses per path element. Worse yet, you either make the ilist a
linked list (in which case, you'll learn what SLOW really means), or it lives
in a known location on disk, meaning that a lost ilist block is a catastrophe.
You could probably make the name/inode organization as robust as the AmigaDOS
organization by following the same file header/block header structure. BTW,
you can loose file names if you loose the file header in AmigaDOS. I think
that's the worst case, though.

Finally, the contention that large directories win with inode/name
organizations - I disagree. Here's where the AmigaDOS caching finally comes
in. Let's assume that a "small" directory requires one block on Unix,
and has no collisions on AmigaDOS. For convenience, assume that "small"
directories are the same size on both systems, and have N file entries
(N for AmigaDOS is 72 (right?); for Unix, it's 32 for v7oid systems,
a minimax of 42 on 4BSD, and probably one of 32/64/128 on sysV). Then access
to a file in a small directory is the same on both systems - 1 disk access.
For a directory that's got M*N entries, it's M/2 (average) on Unix to search
the directory blocks - *not counting the overhead to search the allocation
table*; and M/2 (average) on AmigaDOS to search the hash chain for that entry
 - NO EXTRA OVERHEAD. So AmigaDOS wins by an (over)head :-).

Of course, for listing the files in the directory, AmigaDOS still has
one block/file, plus the directory. Unix keeps getting N files names/block
(again ignoring overhead).

File system design - like the rest of OS design - is non-trivial, and
correct solutions for one application/environment aren't correct - or
even usuable - for another application/environment. The Unix OS on an
Amiga, implemented roughly like the AmigaDOS file system is implemented
(no caching!), would be a total disaster for almost anything. The
AmigaDOS file system isn't perfect for the Amiga environment, and some of
the Unix ideas would be an improvement (the log-tree allocation table and
soft links ('aliases' under AOS, I think) just to start). But I have to
agree with Matt Dillon that what the AmigaDOS file system needs most is
disk caching.

	<mike

wagner@utcs.uucp (Michael Wagner) (05/08/86)

Several mentions have been made now of V1.2.

Would it be possible to get a good, authoritative list of what did and
didn't go into V1.2, including new features and bug fixes?  Presumably,
now that 1.2 is in beta test, this information is relatively firm, and
can be spoken about freely.  I think a lot of people would appreciate
that sort of information.

Oh, and, of course, we'd all like to know when 1.2 would be available to
the general public.

Michael

bruceb@amiga.UUCP (Bruce Barrett) (05/09/86)

In article <636@baylor.UUCP> peter@baylor.UUCP (Peter da Silva) writes:
>> Cheap directories are important on a small-disk machine.  And at least this
>> method allows for essentially unlimited directory sizes, unlike other DOS
>> systems popular on microcomputers today.
>
>I don't know of any DOS that doesn't allow unlimited directory sizes, [...]
	Apple-][ DOS (not Prodos), TRS-DOS, CP/M, MS-DOS (setable, but finite)

>I do think that giving each icon a seperate file is a mistake, since it makes
>folder displays unbearable slow. Why not do what the Integrated Solutions
>system does (more or less) and put all the icons in a folder in a single file
>in that directory?
	One reason might be that you could not just use CLI file copies
to move your files arround.  The copy program(s) would have to keep track
of and update (insert, change, delete) the Icon file for every file copy.

--Bruce Barrett

brent@orsvax1.UUCP (Brent Chivers) (05/09/86)

> I don't know of any DOS that doesn't allow unlimited directory sizes,

According to the VIC-1541 Single Drive Floppy Disk User's Manual
(the drive used by the Commodore 64 and VIC-20):

Figure 1.1	Specifications
STORAGE		Directory Entries	144 per diskette

Tables 5.2 and 5.3 show the directory structure as a linked list, so
I guess the limiting factor (if the manual is correct) must be in the
1541's internal ROM DOS code routines.

(I've never come anywere near the 144-file limit on a 170K disk. :-)
-- 
Brent Chivers		allegra!princeton!orsvax1!brent		or perhaps
ORS Automation, Inc	seismo!caip!topaz!pyrnj!orsvax1!brent
440 Wall St			Phone 609-924-1667
Princeton, NJ  08540		FAX   609-924-2413
USA				TELEX 4944924 ORSIN
-------------
Disclaimer:	Our business is vision, but my views are my own.

daveh@cbmvax.cbm.UUCP (Dave Haynie) (05/12/86)

In article <636@baylor.UUCP> peter@baylor.UUCP (Peter da Silva) writes:
>I don't know of any DOS that doesn't allow unlimited directory sizes...

CP/M, MS-DOS, and GEMDOS to start with.
-- 

Dave Haynie    {caip,inhp4,allegra,seismo}!cbmvax!daveh
               "There, beyond the bounds of your weak imagination
                Lie the noble towers of my city, bright and gold"
								-Genesis

peter@baylor.UUCP (Peter da Silva) (05/15/86)

> In article <636@baylor.UUCP> peter@baylor.UUCP (Peter da Silva) writes:
> >> Cheap directories are important on a small-disk machine.  And at least this
> >> method allows for essentially unlimited directory sizes, unlike other DOS
> >> systems popular on microcomputers today.
> >
> >I don't know of any DOS that doesn't allow unlimited directory sizes, [...]
> 	Apple-][ DOS (not Prodos), TRS-DOS, CP/M, MS-DOS (setable, but finite)

OK, I don't know any serious DOS that allows (not even supports) multitasking
that doesn't allow infinite directory sizes. MS-DOS directories, other than
the root directory, can grow like any other file to any size you want. The
other DOS-es you mention are jokes... (so is MS-DOS, really).

The real competitors of AmigaDOS, and what you should be comparing it with,
are the likes of UNIX and OS/9.

And UNIX directories are just as cheap as yours. As any number of people
have mentioned: you have to put the file name *somewhere*.

> >I do think that giving each icon a seperate file is a mistake, since it makes
> >folder displays unbearable slow. Why not do what the Integrated Solutions
> >system does (more or less) and put all the icons in a folder in a single file
> >in that directory?
> 	One reason might be that you could not just use CLI file copies
> to move your files arround.  The copy program(s) would have to keep track
> of and update (insert, change, delete) the Icon file for every file copy.

They have to keep track of the .info files, don't they? You mean you have to
go back & move the .info files as well? And then change them with your .info
editor if you changed the file name?

Hey... the Amiga is a great machine, and I lust after it. I just think that
there are several places in the system where you didn't really look at the
wealth of existing solutions to a problem like "how do I find a file" before
doing it your own way. Since the O/S interface and implementation seem to be
fairly loosely coupled it should be possible to change things like this
without breaking existing software. So why not just fix it and have done
with it, instead of making excuses? Just putting the filename in the
directory should do wonders for the speed of icon display...
-- 
-- Peter da Silva
-- UUCP: ...!shell!{baylor,graffiti}!peter; MCI: PDASILVA; CIS: 70216,1076