carrotsearch / hppc Goto Github PK

Next to the forEach method we have now, we could have a version with [type]Predicate as an argument. The predicate-based version would be similar to jQuery.each: if the predicate returns true, the iteration will be finished (equivalent of break), for false, the iteration will continue (equivalent of continue).

Issue: HPPC-9 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Mar 10 2010

The following code:
IntIntOpenHashMap map = new IntIntOpenHashMap();
map.put(1, 69);
System.out.println("Size "+map.size());
System.out.println("Get: "+map.get(1));
map.clear();
System.out.println("New Size "+map.size());
System.out.println("New Get: "+map.get(1));

Prints:
Size 1
Get: 69
New Size 0
New Get: 69

The same thing happens with other primitive maps (LongLong, etc). Maps with objects (e.g. LongObject) seem to be working fine, though.

Issue: HPPC-45 (migrated from JIRA), created by Pedro, resolved Feb 03 2011

An indirect hash set of map would allow one to store int-identified data of any kind. Comparisons would be done via a proxy object (and int IDs).

Issue: HPPC-38 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved May 06 2013

I think it makes sense to have an integration layer with Google Collections/Guava as part of HPPC. I'm specifically thinking of some sort of adapters to their Function and Predicate utilities.

Issue: HPPC-4 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Apr 11 2011

HPPC unit tests cover the code pretty well, except for cases when assertions fail. It would be good to have that for completeness as well.

Issue: HPPC-17 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Jul 08 2013

As I said in #44, it's not easy to determine the contents of a BitSet looking at its 64-bit words in a debugger ;-)

Issue: HPPC-35 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Dec 15 2010

Issue: HPPC-30 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Apr 28 2010
Linked issues:

• CARROT-667

I think we once had a similar issue in Carrot2.

Issue: HPPC-39 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Mar 10 2011

Issue: HPPC-11 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Feb 19 2010

removeFirst -> removeFirstOccurrence
removeLast -> removeLastOccurrence

plus overloads for:
removeAll

Issue: HPPC-16 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Feb 19 2010

The toString() method is extremely useful when debugging in an IDE. Deciphering the contents of a BitSet based on the 64-bit mask is for the really hard-core assembly programmers ;-)

Issue: HPPC-1 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Mar 10 2010

Put archive contents in a root directory along the lines of hppc-0.2.0/, which makes unpacking less annoying.

Issue: HPPC-24 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Apr 27 2010

JDK7 introduces new sorting algorithms: dual pivot quicksort and "tim's merge sort". Evaluate on synthetic data and see what the difference is.

http://gdtoolbox.com/DualPivotQuicksort.pdf

–

I created a benchmark against sun-jdk1.7.0_ea_b104. The benchmark tried to compare "new" vs. "old" implementation of Collections.sort() first; on nearly-sorted strings, representing integers from 0..1000000:

        benchmark    ms linear runtime
       LegacySort  39.5 ===
          NewSort  25.3 ==

this turns out really well compared to IndirectSort:

        benchmark    ms linear runtime
IndirectMergeSort  63.7 ======
IndirectQuickSort 313.3 ==============================
       LegacySort  39.5 ===
          NewSort  25.3 ==

but there is a catch: that was nearly sorted data. The same benchmark, but executed on 1.6_20 shows hotspot improvements have been made as well, not only algorithmic improvements (I assume LegacySort didn't change between 1.6 and 1.7; haven't verified this):

        benchmark    ms linear runtime
IndirectMergeSort  63.5 =====
IndirectQuickSort 317.8 ==============================
       LegacySort  53.3 =====
          NewSort  53.2 =====

Very similar results from jrockit:

        benchmark    ms linear runtime
IndirectMergeSort  69.6 =====
IndirectQuickSort 396.9 ==============================
       LegacySort  60.5 ====
          NewSort  60.2 ====

vm: c:\java\jrmc-4.0.0-1.6.0\bin\java.exe

The second benchmark changed the scenario: I randomized the input so it wasn't nearly sorted and I changed Collections.sort() to Arrays.sort() calls to run on Integer[] arrays with a custom comparator, simulating IndirectSort's functionality. This yields, from 1.7:

        benchmark   ms linear runtime
IndirectMergeSort  785 ====================
IndirectQuickSort  918 =======================
       LegacySort 1156 =============================
          NewSort 1163 ==============================

Ok, much more sensible.

Conclusions: if data is nearly sorted and can be reordered, stick to Collections.sort(). If data is randomized and you don't want to reorder the input (for whatever reason), use IndirectSort.

Issue: HPPC-33 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Mar 14 2011

This should increase the usability of the JavaDocs a little.

Issue: HPPC-13 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Feb 19 2010

Apparently there is a stronger check for inheritance hierarchy between filtermapper/filterchains.

Issue: HPPC-15 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Feb 19 2010

There is actually a comment in the code about this (ObjectArrayList):

• The actual value in this field is always <code>Object[]</code>, regardless of the
• generic type used. The JDK is inconsistent here too – {@link ArrayList} declares
• internal <code>Object[]</code> buffer, but {@link ArrayDeque} declares an array of
• generic type objects like we do. The tradeoff is probably minimal, but you should
• be aware of additional casts generated by <code>javac</code>
• when <code>buffer</code> is directly accessed - these casts may result in exceptions
• at runtime. A workaround is to cast directly to <code>Object[]</code> before
• accessing the buffer's elements.

but this can't stay this way indeed, it's weird. I'll look for a workaround.

Issue: HPPC-46 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Feb 17 2011

• Either change site template to point from the overview page to all reports (pmd, cpd, findbugs, clover) or create a custom overview page. [done, added an overview]
• Prepare a dir assembly with stuff that should be rsync'ed to labs site. Add a publish profile which rsyncs these to labs (probably via ANT again?).
• Mavenize other projects in HPPC trunk folder (as sub-modules?).

Issue: HPPC-42 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Mar 01 2011

Issue: HPPC-20 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Mar 08 2010

Dep. update: JUnitBenchmarks, 0.2.1

Issue: HPPC-44 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Jan 25 2011

More people will be unaware of the penalty bad data distribution may bring to hash table performance. java.util.HashMap seems to anticipate this too and rehashes whatever keys are given to it internally. HPPC can use a good hashing function as the default and allow folks to use JDK-compliant (or other) hashes if their data distribution is known.

Rename classes to follow the Object* naming scheme as part of this task.

Issue: HPPC-23 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Mar 12 2010

As suggested by Luc Hogie:

Hi Dawid,

One suggestion for improvement:

addAll(ObjectContainer)

should be

addAll(Iterable<ObjectCursor>)

And, for handiness purpose, I think the addAll() method should be defined in ObjectContainer or ObjectCollection.

Luc.

Issue: HPPC-50 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Mar 11 2011

Example test code:

IntObjectOpenHashMap<String> m1 = new IntObjectOpenHashMap<String>();
m1.put(2, "x");
IntObjectOpenHashMap<String> m2 = new IntObjectOpenHashMap<String>();
m2.put(3, "x");
m1.equals(m2); // returns true
m2.equals(m1); // returns true

Issue: HPPC-37 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Dec 15 2010

A set of interfaces for dealing with collections was added to HPPC. The interfaces are similar, but not identical to JCF. In particular, higher-level interfaces only expose iteration over data (iterable, forEach closures) and data removal (removeAll and other methods). Methods adding data to the collection are pushed down to the level of a particular implementation (because their semantics is defined at that level). Example: a queue has addFirst/addLast, but a list has add().

Issue: HPPC-5 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Mar 10 2010

Tasks related to the initial release:

• JavaDocs

  • Add Carrot Search logo
  • Add Google Analytics

• Website:

  • Add downloads page
  • Add Google Analytics
  • Add information for Maven users
  • Add social stuff (post on Twitter and Digg buttons)
  • Set up discussion group
  • Add information about the license
  • Add "donate" buttons
  • Automatic syncing of artifacts to the website server

Issue: HPPC-14 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Mar 03 2010

Create a mavenized project layout, just to see how it'd compare to the ANT-only version.

Issue: HPPC-41 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Jan 24 2011

Issue: HPPC-32 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved May 24 2010
Linked issues:

• #68

Issue: HPPC-18 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Mar 05 2010

Full POM information, including dependencies available via Maven Central so that
no other repositories are needed.

HPPC is now built with Maven (with ANT snippets).

Issue: HPPC-43 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Jan 25 2011

Compaction does affect get() performance with many removed elements.

Issue: HPPC-48 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Apr 23 2011

Particularly useful for arrays. Let's say you want to make a set of char[] instances. They are objects, but they don't override equals. You must therefore provide a wrapper, which is a memory overhead.

Issue: HPPC-25 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved May 19 2010
Linked issues:

• #75
• #74

It's interesting to me that for (IntCursor c : <IntContainer>) is nearly always significantly slower than a simple loop over the indices of a given container. Check why is this the case and what can be done to improve this situation for simple loops.

Issue: HPPC-27 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Apr 27 2010

Issue: HPPC-29 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Apr 30 2010

Issue: HPPC-12 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Mar 12 2010

Issue: HPPC-22 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Apr 27 2010

I think we could follow the JCF convention and have two methods:

[type]ArrayDeque.descendingIterator()
[type]ArrayDeque.descendingForEach([type]Procedure)

Issue: HPPC-3 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Feb 19 2010

This would make the API more JCF-like. There are two strategies to implement this method:

• dependent on #48: retainAll() would take an implementation of [type]Collection interface and use its contains() method
• independent of #48: retainAll() would take a [type]Iterator just like other similar methods and internally use a temporary set (e.g. BitSet) to track the values we want to keep or remove

Issue: HPPC-6 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Mar 10 2010

Add generic signature to ObjectHashFunction for nicer overrides.

Issue: HPPC-31 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved May 19 2010
Linked issues:

• #68

Issue: HPPC-26 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Apr 27 2010

Indirect sorting routines are very useful in many applications and they are missing from the JDK. I'll move Carrot2 implementation to HPPC.

Issue: HPPC-21 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Mar 12 2010

The default load factor is always used, instead of the field.

Issue: HPPC-19 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Mar 05 2010

fastutil is ASL licensed and contains MurmurHash3. It only applies the finalization step, the q is if it's enough for robust bit spreading.

Issue: HPPC-47 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Mar 04 2011

This would make the Sets compatible with ArrayLists. We may also want to add the same methods to ArrayDeques (addFirst(type, type), addLast(type, type)).

Issue: HPPC-7 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Feb 19 2010

http://en.wikipedia.org/wiki/Xorshift

Oh, so simple and yet so nice.

Issue: HPPC-49 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Mar 11 2011

Currently, Lists have the removeAll(type e) method that removes all elements that are equal to e. It would be good to generalize this method to become removeAll([type]Predicate) and have it remove all elements for which the predicate returns true.

Would it make sense to have this method in all Lists, Sets and Deques?

Issue: HPPC-8 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Mar 10 2010
Attachments: HPPC-8.patch

Issue: HPPC-34 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Mar 11 2011

Oh, this is such a neat idea. It is often the case that you need to collect or compute something and then return the value back to the surrounding context. Doing this can be achieved in a number of ways – field reference, shared object, final local array, etc., but a much nicer alternative is to allow the caller to read the result directly from the fields or methods of the argument class. This works even if the argument class is anonymous, as in this example:

int count = container.forEach(new IntProcedure() {
    int count;
    public void apply(int value) { count++; }
}).count;

Changing the current method signatures in forEach is backward compatible.

Issue: HPPC-36 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Dec 15 2010

One primitive type that is not yet supported is boolean. While some collections involving booleans, such as BooleanSet or BooleanBooleanMap, would be of limited use, some others, such as BooleanList or IntBooleanMap, seem very reasonable.

Issue: HPPC-2 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Feb 18 2010

Judging by the behaviour of the code that uses IndirectSort.mergesort, the sorting appears to be stable, but additional look at the code wouldn't hurt.

Issue: HPPC-40 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Mar 13 2011

HPPC seems hardcore enough that we can assume that developers know what the consequences of varargs are. In the future, JVMs may be able to handle varargs without temporary arrays.

Issue: HPPC-10 (migrated from JIRA), created by Stanisław Osiński (@stanislawosinski), resolved Feb 19 2010

Issue: HPPC-28 (migrated from JIRA), created by Dawid Weiss (@dweiss), resolved Apr 28 2010