Package net.algart.arrays

See:
          Description

Package net.algart.arrays Description

Defines AlgART arrays: generalized arrays of any Java types.

AlgART arrays are classes allowing to store one- or multi-dimensional random access arrays, containing elements of any Java type, including primitive types.

AlgART arrays are homogeneous: the type of elements of an array are the same (for primitive elements) or are inheritors of the same class (for non-primitive elements). AlgART arrays, unlike standard Java arrays, may be resizable: you may add elements to the array end or remove some elements at any time.

AlgART arrays include all basic functionality of the standard Java ArrayList class and of Java NIO buffers, but also provide a lot of new features.

The basic AlgART array interface is Array: read-only one-dimensional array with any element type. There are a lot of its subinterfaces with additional functionality and restrictions.

Contents

• Main features of AlgART arrays
• The diagram of interfaces and implementations
• The maximal supported array length
• 5 levels of protection against unallowed changes
• Multithreading and synchronization
• Runtime exceptions and errors
• System properties used for customizing AlgART arrays
• Built-in logging
• Tasks that are better solved by standard Java collections

Main features of AlgART arrays

1. The addressing of array elements is 63-bit. So, it's theoretically possible to create and process arrays containing up to 2⁶³-1 (~10¹⁹) elements of any primitive or non-primitive types, if OS and hardware can provide necessary amount of memory or disk space. Please see also the section "The maximal supported array length" below.
    
2. Multi-dimensional arrays, named "matrices", are supported via the Matrix interface. Any one-dimensional array can be viewed as a matrix and vice versa.
    
3. AlgART arrays are implemented with help of special factories, named Virtual Memory Models (MemoryModel interface), that provide a standard way of implementing any schemes for storing data, from simple Java arrays to mapped disk files. The current implementation offers 4 basic memory models:
   • the simplest and fastest Simple memory model, that stores data in usual Java arrays;
   • Buffer memory model, that use Java NIO buffers for storing data: it does not provide the maximal access speed, but can provide better overall performance in applications that require large amount of RAM, and also provides good compatibility with Java code working with channels and NIO buffers;
   • advanced Large memory model, that may store large amount of primitive elements in mapped-files — it is the only way (in current Java versions) to create very large arrays, containing, theoretically, up to 2⁶³-1 elements;
   • special Combined memory model, allowing efficient storing non-primitive elements in a set of another arrays — together with LargeMemoryModel, it allows to store more than 2³¹-1 non-primitive elements in one array.
   Moreover, the Large memory model is based on special low-level factories, named Data File Models (DataFileModel interface). Creating non-standard data file models allows to easily implement storing array elements in almost any possible devices or storages. For example, it's possible to create data file model that will represent a content of BufferedImage as AlgART array.
    
4. Arrays implement maximal efficient memory usage. In particular, AlgART arrays allow to use only 1 bit per element while storing boolean values, 4 bytes per elements while storing int or float values, or 3*4=12 bytes per element while storing Java objects consisting 3 int field, as for the following Circle object:

    class Circle {
        int x;
        int y;
        int r;
    }
    

   Unlike this, Java NIO buffers allow efficient storing only non-boolean primitive elements, and standard ArrayList always stores every element as a separate instance, that require a lot of extra memory for simple structures.
    
5. There are separate interfaces for almost all kinds of data access that makes usage of arrays more simple and stable. Namely, there are separate interfaces for read-only access (Array), read-write access without changing the array length (UpdatableArray), stack access — adding and removing the last element (Stack), and full access including resizing the array (MutableArray). In addition, there are DataBuffer interface, providing convenient and maximally efficient block access to AlgART arrays, and DirectAccessible interface for quick access to internal Java array if the elements are really stored in an underlying Java array. There is also full set of interfaces for quick and convenient access to elements of all primitive types.
    
   This architectural solution allows safe programming style, when illegal array operations are syntactically impossible. For example, the methods, which process an AlgART array argument and calculate some results, but don't need any modifications of the passed array, declare their array argument as Array or XxxArray, where Xxx is Byte, Int, Float, ... — interfaces containing only reading, but not writing methods. The methods, which correct the array content, but don't need to add or remove array elements, declare their array argument as UpdatableArray (or UpdatableXxxArray) — interfaces containing only reading and writing, but not resizing methods. This solution allows to avoid "optional" operations, used for implementation of read-only arrays in standard Java libraries.
    
6. The AlgART arrays architecture offers advanced means for protection against unallowed changes of the array content. Namely, any array can be cloned (the simplest protection), converted to immutable form, to more efficient (in some cases) trusted immutable form or to special quite safe copy-on-next-write form. Also, any resizable array can be converted to unresizable form, which length is fixed. Using read-only Array or unresizable UpdatableArray interfaces (and their inheritors for primitive types), instead of the full MutableArray, also helps to avoid unwanted operations.

The diagram of interfaces and implementations

The basic set of AlgART array interfaces and classes can be represented as 3-dimentional structure. The 1st dimension corresponds to the type of elements: there are separate interfaces and classes for all 8 primitive Java types and for Object type (and its inheritors). The 2nd dimension describes the array functionality: read-only access (Array), read/write access (UpdatableArray), full access including resizing (MutableArray), quick access to internal Java array (DirectAccessible). The 3rd dimension is the Virtual Memory Model: the scheme of storing array elements.

Below is a diagram of basic array interfaces and classes.

There are special superinterfaces for some groups of primitive types, allowing to specify any array with elements from such groups. The hierarchy is the following:

• Array subinterfaces:
  • PArray subinterfaces:
    • PFixedArray subinterfaces:
      • BitArray
      • CharArray
      • PIntegerArray subinterfaces:
        • ByteArray
        • ShortArray
        • IntArray
        • LongArray
    • PFloatingArray subinterfaces:
      • FloatArray
      • DoubleArray
  • ObjectArray

Also, all subinterfaces of PFixedArray and PFloatingArray are grouped into the common interface PNumberArray (any primitive types excepting boolean and char, alike java.lang.Number class).

There are the same hierarchies for updatable and mutable arrays, but not for stacks.

The maximal supported array length

The maximal possible length of AlgART array depends on the memory model that has created this array. An attempt to create an array with length exceeding the limit, specified by the memory model, or an attempt to increase the length or capacity of an existing array over this limit, leads to TooLargeArrayException (instead of the usual OutOfMemoryError).

The maximal array lengths for different memory models are listed below.

5 levels of protection against unallowed changes

There is an often and important problem to protect some application data against unallowed changes, to avoid hard bugs connected with unexpected damage of application objects. Below is a typical code illustraging this problem:

 DataClass a = ...; // some important data
 someResults = someObject.process(a); // some method that need read-only access to the argument
 

Here a is some "important" data, that must stay immutable while the following call of process method. Maybe, for example, some parallel threads are reading this object now. And someObject.process is a method, which, theoretically, should not correct the passed data: it only analyzes it and creates some result. But it's very possible, that we are not sure, that this method really fulfils it. Maybe, its implementation is downloaded from Internet (and can be written by a hacker to damage our application). Or this method performs very complex tasks, and we cannot be sure that it doesn't contain bugs.

Java arrays offer only one way to protect data against changes and to solve this issue: cloning an array. An example:

 int[] a = ...; // some important array
 int[] protected = (int[])a.clone();
 someResults = someObject.process(protected);
 

Here the process method may corrupt the passed argument, but the original array will stay unchanged.

Standard Java collections, as well as buffers from java.nio packages, offer an additional method: making an immutable view. For example:

 List a = ...; // some important list
 List protected = Collections.unmodifiableList(a);
 someResults = someObject.process(protected);
 

Now, if the process method will try to correct the passed argument, an exception will be thrown. This solution has an advantage: no additional memory is required for storing a clone.

AlgART array architecture supports 5 ways for solving this task, including 2 ways described above. We shall compare all them below.

1. Syntactical protection

The 1st solution is the simplest, fastest, but not safe enough. It is a syntactical solution. If the process method does not need to modify its argument, it should be declared with Array argument type, which doesn't contain any mutation methods at all:

 public ResultType process(Array a);
 

A usage example:

 Array a = ...; // maybe, there is MutableArray in this expression
 someResults = someObject.process(a);
 

Of course, it is not a problem to write a "malicious" process method which will correct its argument by operators alike the following: ((MutableArray)a).set(0, ...). However, if process method is written by you or by your colleagues, and you only need to protect against possible bugs, the syntactical protection will help you.

2. Cloning

It is a very simple and absolutely safe solution:

 Array a = ...;
 Array protected = a.updatableClone(); // or a.mutableClone()
 someResults = someObject.process(protected);
 

Unfortunately, such a solution requires additional memory and time, even if the process method, really, does not try do modify its argument.

3. Immutable view

It is a traditional, also simple and absolutely safe method, used by standard Java collections and NIO buffers:

 Array a = ...;
 Array protected = a.asImmutable();
 someResults = someObject.process(protected);
 

The difference from the analogous technique, implemented in standard Java libraries, is absence of "optional" operations. In a case of Java collections, process method will have an ability to call a mutation method for the passed array, but this method will throw an exception. Unlike this, Array.asImmutable() method returns an object that does not implement any interfaces and does not contain any methods, which allow to change data anyhow.

The main defect of this solution is disabling any possible optimization, based on direct access to stored data. For example, DirectAccessible interface may allow access to the Java array, internally used for storing elements. If process method needs a lot of accesses to elements in random order, then using DirectAccessible interface in a separate algorithm branche can optimize the method in times, in a case when the AlgART array is really based on Java arrays. Unfortunately, an immutable view has no right to provide such direct access to internal storage, because it is a possible way to corrupt the array.

4. Trusted immutable view

It is a compromise between absolute safety, provided by cloning and immutable views, and maximal efficiency, achieved while using syntactical protection only. An example of usage:

 Array a = ...;
 Array protected = a.asTrustedImmutable();
 try {
     someResults = someObject.process(protected);
 } finally {
     protected.checkUnallowedMutation();
 }
 

Unlike usual immutable view, a trusted immutable view may implement some interfaces, that allow to change the array content — only if it is really necessary for optimization. (The only example of such interface in this package is DirectAccessible.) So, the process method may corrupt the original array a. However, any changes in the original array will be detected by the following call "protected.checkUnallowedMutation()" with almost 100% probability, and if the array was changed, UnallowedMutationError will be thrown. To detect changes, checkUnallowedMutation usually calculates a hash code and compares it with the hash code calculated in asTrustedImmutable method.

This technique is a suitable solution if you trust the authors of process method (for example, it is written by you or your colleagues), but this method is not trivial and you are not sure that all possible bugs in this method are already fixed. Unlike all other 4 protection methods, it is the only way to automatically detect such bugs: so, trusted immutable views may be very useful in a stage of testing application.

This solution have the following defects.

• It requires little additional time (for calculation of hash code) while calling asTrustedImmutable() and checkUnallowedMutation() methods. (However, as well as immutable views, this method does not require any additional memory.)
• If there are another threads working with the original array, then the unallowed changes of elements can lead to errors in that threads before detecting these changes and throwing UnallowedMutationError.
• This method protects against algorithmic bugs, but not against a malicious method, specially written by a hacker. If the author of the method have read the source code of this package, it can perform changes of the array, which will not be detected by this technique.

5. Copy-on-next-write view

It is a more efficent alternative to cloning an array. This solution is also absolutely safe, but, sometimes, it requires additional memory and time. An example:

 Array a = ...;
 Array protected = a.asCopyOnNextWrite();
 someResults = someObject.process(protected);
 

Now process method may freely change the passed argument (if it implements necessary interfaces). However, the first (not further!) attempt to modify the passed protected array, or any other access that can lead to its modification (like DirectAccessible.javaArray() method), will lead to reallocation of the underlying storage, used for array elements, before performing the operation. It means that modification will not affect the original a array, but only protected array.

This solution is the best choince, if you need a strict guarantee that the original array will not be modified (that is not provided by trusted immutable views), and you don't need a guarantee that no additional memory will be occupied. If the process method will not try to modify the array or use optimization interfaces alike DirectAccessible, then this solution will provide the maximal efficiency. If the method will try to get direct access for optimization via DirectAccessible interface, then the internal data will be cloned at this moment, that can require additional memory and time, but all further accesses to elements will work with maximal efficiency.

This solution have the following defects.

• It is not better than simple cloning, if the processing method always use the direct access to the storage for optimization goals (for example, via DirectAccessible interface), and the passed array really allows this optimizaion (for example, is based on Java arrays). Good processing methods may use Array.isCopyOnNextWrite() method to choose the best behaviour.
• It does not help to detect bugs that lead to unallowed changes of array elements. But you may use this techique together with trusted immutable view: "Array protected = a.asCopyOnNextWrite().asTrustedImmutable()" Such protection is also absolutely safe, but also allows to catch unallowed attempts of correction by checkUnallowedMutation() method.

Multithreading and synchronization

Immutable AlgART arrays are absolutely thread-safe and can be used simultaneously in several threads. Moreover, even if an AlgART array is mutable (for example, implements MutableArray), but all threads, accessing it, only read data from it and do not attempt to modify the array by any way, then this array is also thread-safe and no synchronization is required. (The same rules are correct for usual Java arrays.)

If there are 2 or more threads accessing an AlgART array, and at least one from them modifies it (for example, changes elements or the length), then you should synchronize access to the array. Without external synchronization, the resulting data in the array will be unspecified. However, if you do not use any methods from MutableArray / Stack interfaces and their inheritor, but only read and write elements via methods provided UpdatableArray interface (and its versions for concrete element types), then the behaviour while simultaneous multithreading access will be the same as for usual Java arrays. In particular, access to one element will never affect another elements. So, you can correctly simultaneously work with several non-overlapping sets of elements of the same array from several threads without synchronization, if different threads work with different sets. (Please compare: the standard java.util.BitSet class does not provide such guarantees.)

Runtime exceptions and errors

The methods of classes implementing AlgART arrays, usually, may throw exceptions declared in the Javadoc comments to methods. In addition, there are following exception, that may be thrown by methods and are not always specified in comments.

• java.io.IOError may be thrown at any moment by any method processing an AlgART array (as well as OutOfMemoryError may be thrown my almost any Java method). java.io.IOError is usually thrown when an array is based on some external file, as in the Large memory model, and there is some problem with access to this file, for example, not enough disk space.
   
  One of the typical situations leading to this error is unexpected program termination, when some threads work with arrays created by Large memory model. In this case, the built-in shutdown hook is started to remove all temporarily allocated disk files, and since it is started, almost any access to an AlgART array, based on a temporary file, lead to IOError with IllegalStateException as a cause.
   
  Warning: java.io.IOError may be also thrown while processing an AlgART array, based on some external file, as in the Large memory model, if the current thread is interrupted by Thread.interrupt() method. Also this error is thrown if the Thread.interrupt() method is called for a thread, that is currently performing multithread copying by copy method. Usually, such behaviour is not suitable. So, you should not try to interrupt the threads, processing AlgART arrays, via Thread.interrupt() technique! Please use an alternative technique: some volatile flag, required interruption, or net.algart.contexts.InterruptionContext interface. For interruption of Arrays.copy method, you may also use the custom implementation of ArrayContext.
   
• Any RuntimeException may be thrown by Arrays.copy method, if the context, passed to this method, throws this exception in its checkInterruption() method. It is the recommended way of interrupting Arrays.copy method.
• java.io.IOError was added since JDK 1.6 only. Under Java 1.5, the similar net.algart.arrays.IOErrorJ5 exception is thrown instead. This error is package-private and may be excluded in future versions of AlgART libraries.
   
• AssertionError may be thrown at any time if some bug will be auto-detected in AlgART libraries. Some internal checks (that can lead to this error in a case of the bug) are skipped when Java is started without -ea flag. The most serious bugs, if they will be auto-detected, lead to InternalError instead of AssertionError. We hope that these errors will not be thrown inside this package in applications.
   

System properties used for customizing AlgART arrays

Behaviour of AlgART arrays depends on some system properties, that allow to customize many important aspects. Below is the list of these properties.

"net.algart.arrays.globalMemoryModel"

Defines the default memory model, that may be used in your classes which need AlgART arrays. The simple memory model is used by default. See Arrays.SystemSettings.globalMemoryModel() for more details.

"net.algart.arrays.maxTempJavaMemory"

Defines the maximal amount of usual Java memory, in bytes, which may be freely used by methods, processing AlgART arrays, for internal needs and for creating results. May contain any nonnegative long value. Default value is 33554432 (32 MB). See Arrays.SystemSettings.maxTempJavaMemory() for more details.

"net.algart.arrays.maxMultithreadingArraySize"

Defines the maximal size of AlgART array, in bytes, when multithreading processing is recommended. May contain any nonnegative long value. Default value is Long.MAX_VALUE (i.e. this limit is not used). See Arrays.SystemSettings.maxMultithreadingArraySize() for more details.

"net.algart.arrays.maxMappedMemory"

Defines the maximal amount of system memory, in bytes, allowed for simultaneous mapping by DefaultDataFileModel class. May contain any nonnegative long value. Default value is 268435456 (256 MB). See DefaultDataFileModel.maxMappedMemory() for more details.

"net.algart.arrays.CPUCount"

Defines the number of processors that should be used for multithreading optimization. If not exists, or zero, or negative, then Runtime.getRuntime().availableProcessors() will be used instead. See DefaultThreadPoolFactory.recommendedNumberOfTasks() for more details.

"net.algart.arrays.globalThreadPoolSize"

Defines the number of threads in the global system thread pool that will be used for multithreading optimization. If zero or negative, then the thread pools will be created on demand. If not exists, the global thread pool with 128 threads (default value) will be used. See DefaultThreadPoolFactory.globalThreadPool() for more details.

"net.algart.arrays.profiling"

Defines whether the algorithms, processing AlgART arrays, should write to logs some timing information. May be "false" or "true". Default value is false. See Arrays.SystemSettings.profilingMode() for more details.

"net.algart.arrays.LargeMemoryModel.dataFileModel"

Defines the default data file model, used by the Large memory model. DefaultDataFileModel is used by default. See LargeMemoryModel.getInstance() for more details.

"net.algart.arrays.DefaultDataFileModel.numberOfBanksPerCPU"

Defines the number of banks per each existing CPU or CPU kernel, used by the default data file model. Default value is 3. See DefaultDataFileModel.recommendedNumberOfBanks() for more details.

"net.algart.arrays.DefaultDataFileModel.bankSize"

Defines the size of banks, used by the default data file model for unresizable arrays (on 64-bit Java machines). Default value is 4194304 (4 MB). See DefaultDataFileModel.recommendedBankSize(boolean) with true argument for more details.

"net.algart.arrays.DefaultDataFileModel.resizableBankSize"

Defines the size of banks, used by the default data file model for resizable arrays (on 64-bit Java machines). Default value is 262144 (256 KB). See DefaultDataFileModel.recommendedBankSize(boolean) with false argument for more details.

"net.algart.arrays.DefaultDataFileModel.singleMappingLimit"

Defines the limit for file size, so that less unresizable files are mapped only once in the default data file model (on 64-bit Java machines). Default value is 33554432 (32 MB). See DefaultDataFileModel.recommendedSingleMappingLimit() for more details.

"net.algart.arrays.DefaultDataFileModel.bankSize32"

Defines the size of banks, used by the default data file model for unresizable arrays (on 32-bit Java machines). Default value is 1048576 (1 MB). See DefaultDataFileModel.recommendedBankSize(boolean) with true argument for more details.

"net.algart.arrays.DefaultDataFileModel.resizableBankSize32"

Defines the size of banks, used by the default data file model for resizable arrays (on 32-bit Java machines). Default value is 131072 (128 KB). See DefaultDataFileModel.recommendedBankSize(boolean) with false argument for more details.

"net.algart.arrays.DefaultDataFileModel.singleMappingLimit32"

Defines the limit for file size, so that less unresizable files are mapped only once in the default data file model (on 32-bit Java machines). Default value is 2097152 (2 MB). See DefaultDataFileModel.recommendedSingleMappingLimit() for more details.

"net.algart.arrays.DefaultDataFileModel.autoResizingOnMapping"

Defines whether AlgART mapping manager in the default data file model should increase the file size via standard I/O API, or it is increased automatically as a result of new mappings. Default value is false. See DefaultDataFileModel.autoResizingOnMapping() for more details.

"net.algart.arrays.DefaultDataFileModel.lazyWriting"

Defines whether the default data file model will use lazy-writing mode by default. Default value is true in Java 1.7 or higher Java version and false in Java 1.5 and Java 1.6. See DefaultDataFileModel.DefaultDataFileModel(java.io.File, long) consturctor for more details.

"net.algart.arrays.StandardIODataFileModel.numberOfBanks"

Defines the number of banks, used by the