Gridarta Editor
Classes
Package net.sf.gridarta.model.face

Classes

class  AbstractFaceObjects
 
class  AbstractFaceProvider
 
class  ArchFaceProvider
 
class  CollectedFaceProvider
 
class  ColourFilter
 
class  DefaultFaceObject
 
class  DefaultFaceObjects
 
class  DoubleImageFilter
 
class  DuplicateFaceException
 
class  EmptyFaceProvider
 
interface  FaceObject
 
class  FaceObjectProviders
 
interface  FaceObjectProvidersListener
 
interface  FaceObjects
 
interface  FaceProvider
 
class  FilterFaceProvider
 
class  IllegalFaceException
 
class  StretchedImageFilter
 
class  TestFaceObjects
 

Detailed 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
  1. 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