English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Announcement: automatically resizing arrays
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 1999-10-14 (13:01)
From: Markus Mottl <mottl@m...>
Subject: Announcement: automatically resizing arrays

as promised last week, I have just released my implementation of
automatically resizing contiguous memory (= arrays, strings, etc...).

Here a part of the README explaining the advantages of using it:

  * Fast constant-time access to indexed elements (e.g. in arrays and
    strings) is often a prerequisite for short execution times of

    Still, operations like adding and/or removing elements to/from the
    end of such datastructures are often needed.  Unfortunately, having
    both properties at the same time sometimes requires reallocating
    this contiguous part of memory.

    This module does not eliminate this problem, but hides the process
    of reallocation from the user, i.e. it happens automatically.

    Thus, the user is liberated from this bug-attracting (e.g. index
    errors) task.

  * This library allows the user to parameterize allocation strategies at
    runtime. This is a very important feature, because it is impossible
    for any allocation algorithm to perform optimally without having
    knowledge about the user program.

    For example, the programmer might know that a consecutive series
    of operations will alternately add and remove large amounts of
    elements. In such a case it would be wise to keep a high reserve
    of available slots in the datastructure, because otherwise it will
    resize very often during this procedure which requires a significant
    amount of time.

    By raising a corresponding threshold in appropriate places at runtime,
    the programmer can fine-tune the behaviour of e.g. his buffers for
    optimal performance and set this parameter back later to save memory.

  * Because reallocation strategies themselves may be quite complicated,
    it was also a design goal to have the user supply his own ones
    (if required).

    By using functors the user can parameterize these datastructures
    with his own reallocation strategies, giving him even more control
    over how and when reallocations are triggered.

  * It is possible that the user wants to add support for additional
    low-level implementations that require reallocations (e.g. bit-strings
    have not yet been added to this distribution). Even in this case it
    is fairly easy to create new modules by using functors.

  * The library implements a large interface of functions, all of which
    are completely independent of the reallocation strategy and the
    low-level implementation.

    All the interfaces of the corresponding low-level implementations
    of datastructures (e.g. array, string) are fully supported and have
    been extended with further functionality. There is even a new buffer
    module which can be used in every context of the standard one.

  * OCaml makes a distinction between unboxed and boxed arrays. If
    the type of an array is "int" or "float", the representation will
    be unboxed in most cases.

    To benefit from these much faster representations there are
    specialized versions of automatically resizing arrays in the

The examples in the distribution are fairly short - the documentation
could surely be better (is there something like a perfect
documentation??). If you have questions, comments, etc., feel free to
contact me...

Best regards,
Markus Mottl

Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl