[openbeos] Re: Threading and File Descriptors
- From: François Revol <revol@xxxxxxx>
- To: openbeos@xxxxxxxxxxxxx
- Date: Sat, 17 Aug 2002 10:24:46 +0200 (MEST)
En réponse à "Alexander G. M. Smith" <agmsmith@xxxxxxxxxx>:
> > Pros: Cons:
> > Approach 1: Array
> > Fast Access Fixed amount, space wasted
> > Simple Code Poor insertion and deletion
> >
> > Approach 2: Linked List
> > Fast insertion & deletion Slower access
> > No wasted slots Wasted space (pointers to
> > next)
> > Any number possible (little) more complex code
> >
> > Approach 3: Extensible Arrays
> > Fast Access Complex Code
> > Moderate waste (you don't want to extend the array for every
> insert/delete)
> >
would it be so complex ?
what about having the first part of the array static, and only add parts
if we really need to ?
struct desc {
long count;
struct desc *next;
foobar descs[0];
}
with the first would be inlined in process descriptors or such, and a FOREACH
macro would do
({
foobar *fd;
struct desc *current = &proc[i].fd;
while (current) {
int i;
for (i=0; i < current->count; i++) {
if (compare(current->descs[i], d))
goto found;
}
current = current->next;
}
NULL;
found:
current->descs[i];
})
Of course that's not even quite O(1), and hashing would be harder...
but in the usual case we would not need anny malloc() since the first block
is inlined, and the overhead isn't big.
> > I can't think of any others.
>
> Sorted data structures - trees, skip lists, and other dynamically
> allocated and automatically balancing data structures. Not as fast as
> an array (perhaps 10 times slower than an array lookup, which may sound
> silly but may actually be worth it to get rid of the artificial limits),
> and they have the advantages of a linked list. The key could even be a
> small integer, used as a handle to the data, or a pointer if the nodes
> in the data structure don't move around. The small integer (used much
> like you would an array index but never getting reused for deallocated
> items; always incrementing) is better since invalid key/handles are
> detected.
handles remind me the "good old days" of Mac 68k and Ti92... :)
(they described allocated memory that could be moved until locked to get
a pointer to it)
Maybe worth a try though
>
> > I have many of the same issues in the VM work that I am doing. The
> *average* area will probably
> be <= 256k. So should I optimize for something that size?
>
> And then there are areas which are hundreds of megabytes big. Possibly
> gigabytes if running on a 64 bit processor. Big images (600 dpi scans
> of large things). Big RAM disks (my pet project, 128MB areas aren't big
> enough!). Hours of sound or video in an editor. Maybe even get rid of
> hard drives and just use RAM (particularly if magnetic nonvolatile RAM
> becomes affordable).
>
What about using fixed size arrays, with sizes tweakable at boot
(in ~/config/settings/kernel/drivers/kernel) ?
would be as fast, just need a malloc(), still simple code...
and in case we want to run IceCast for 10000 users just change the MAX_FD
in the kernel prefs and reboot :)
Or we could as well be able to change some (MAX_FD) at runtime, so increasing
it just before running critical progs (there is a defined interface for this,
called ulimit()).
Of course it's not as good as if the system would deal itself with this...
We must keep in mind we are building a desktop OS, not a server :^)
Also remember MAX_FD is defined in POSIX headers, so dynamic growing is maybe
not worth it.
François.
Other related posts:
