-
-
-
Exception Summary
Exception |
Description |
DuplicateFaceException |
Exception that's thrown in case a face name was not unique.
|
IllegalFaceException |
Exception thrown to indicate that a face object is not acceptable.
|
Package net.sf.gridarta.model.face Description
The face is the appearance of an object.
This package contains classes for managing icons in memory sensitive caches.
Currently, the keys to lookup the icons are Strings (usually the facename of an
archetype), and lookup is done in HashMaps.
HashMaps are fast, but, of course, never as fast as an indexed array. Though,
HashMaps are easier to maintain. In case someone complains about the usage of
HashMaps instead of arrays in this package, I have documented my performance
considerations.
- How fast is String hashCode generation?
- Extremely fast. Strings are often used as Hash keys, therefore a
String's hash code is ached and only calculated the first time a it is
queried. All subsequent invocations return the previously calculated,
cached hash code.
- How fast is HashMap lookup compared with Array indexing?
-
To index an Array gives a constant speed of O[array] = O(c)
where c is the time it takes to address and offset. To lookup
in a HashMap gives a performance of approximately O[hashMap] =
O(2*c + log2(n)*c*2) where n is the number of HashMap
entries. In general, a HashMap gives a very good performance, but not
compared with an array when an index can be used.
- How does lookup scale?
-
Lookup is used every time the code needs an image, which is nearly every
time some painting is done by Java. Since maps are 2.5-dimensional
structures, the lookup part of painting maps gives a general performance
of O[paintLookup] = O(O[lookup] * x * y * z). For a map with
the size 24*24 and an average tile coverage of 2 faces requires 24*24*2
lookups which is 1152 lookups. And let n, the number of
HashMap entries, be 3688. If O[lookup] == O[array], the
performance is O[paintLookup] = O(c * x * y * z) = O(c *
1152). If O[lookup] == O[hashMap], the performance is
O[paintLookup] = O((2*c + log2(n)*c*2) * x * y * z) = O((2*c +
log2(3688)*c*2) * 1152) = O((2*c + 24*c) * 1152) = O(c *
29952) It is a realistic assumption that the number of
effective cycles required for performing a lookup in Java is always
smaller than 10 times the performance. That means, a complete map paint
lookup for the given example map takes less than 300,000 cycles when
using a HashMap. Current CPUs execute about 5,000,000,000 cycles per
second.
- How often is lookup needed?
-
Repainting is done when a new tile was painted, the map scrolls, a map
was loaded, hidden or otherwise gets completely refreshed, an archetype
panel scrolls or a pickmap is used. Lookup does not happen more than 2-3
times per second, except for scrolling.
- Other considerations
-
The design to generate artificial indices for faces has some flaws.
Keeping several arrays in parallel to hold the same information can
cause serious, eventually difficult to find bugs. Such a design also
prevents the implementation of dynamic archetype handling, where arches
and faces should be loadable, editable and un-loadable during editor
runtime. The allocation of several large arrays also is a serious
indicator for design flaws when using artificial indices, also these
arrays need to be anxiously oversized to not get into
ArrayIndexOutOfBounds trouble. The natural index of a face is its name,
the object oriented index of a face is its own reference. Mapping face
names to face references therefore is a good and clear design and very
resistant against bugs or overflows.
Also, an archetype first naturally comes with a face name. To get an
index for a face name, it is required to first do a linear search.
Linear search is always wrong and averages to O(n * c) which
is worse than HashMap performance. If the indices are sorted, a binary
search with a performance of O(2*c + log2(n)*c*2), which is
exactly what a HashMap does. That means, the term that best describes
the usage of artificial face indices for increasing face lookup
performance is "Augenauswischerei".
Conclusions
- Do not use the face number for face lookup, use the face name instead.
- Future: Refactor all code to eliminate artificial indices for faces and
arches