Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[4237] branches/QUADS_QUERY_BRANCH/ctc-striterators/src /java/cutthecrap/utils/striterators
|
From: <mar...@us...> - 2011-02-24 09:11:03
|
Revision: 4237
http://bigdata.svn.sourceforge.net/bigdata/?rev=4237&view=rev
Author: martyncutcher
Date: 2011-02-24 09:10:56 +0000 (Thu, 24 Feb 2011)
Log Message:
-----------
Related to ticket 243 and 244 after analysis of performance of deep striterations and implementing a generic prefetch pattern that allows efficient processing of hasNext for such structures. Associated is a tail optimisation that enables the collapse of the stack-based invocations analagous to tail recursion optimisation in functional programming.
Modified Paths:
--------------
branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Appenderator.java
branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Contractorator.java
branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Expanderator.java
branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Filterator.java
branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/IStriterator.java
branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Striterator.java
Added Paths:
-----------
branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Prefetch.java
Modified: branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Appenderator.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Appenderator.java 2011-02-24 01:04:12 UTC (rev 4236)
+++ branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Appenderator.java 2011-02-24 09:10:56 UTC (rev 4237)
@@ -21,59 +21,70 @@
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
-*/
+ */
package cutthecrap.utils.striterators;
import java.util.*;
+import cutthecrap.utils.striterators.IStriterator.ITailOp;
+
/**
* Appenderator
**/
-public class Appenderator implements Iterator {
+public class Appenderator extends Prefetch implements ITailOp {
private final Iterator m_src;
- protected final Object m_ctx;
+ protected final Object m_ctx;
private final Iterator m_xtra;
-
+
private Iterator m_current;
+ private boolean m_isxtra = false;
- public Appenderator(Iterator src, Object ctx, Iterator xtra) {
- m_src = src;
- m_ctx = ctx;
- m_xtra = xtra;
+ public Appenderator(Iterator src, Object ctx, Iterator xtra) {
+ m_src = src;
+ m_ctx = ctx;
+ m_xtra = xtra;
- m_current = m_src;
- }
+ m_current = m_src;
+ }
- //-------------------------------------------------------------
+ // -------------------------------------------------------------
- public boolean hasNext() {
- if (m_current.hasNext()) {
- return true;
- } else if (m_current == m_xtra) { // don't call twice
- return false;
- }
-
- m_current = m_xtra;
-
- return m_current.hasNext();
- }
+ protected Object getNext() {
+ Object ret = null;
+ if (m_current.hasNext()) {
+ ret = m_current.next();
+ } else if (m_isxtra) { // no need to call twice
+ return null;
+ } else {
+ m_current = m_xtra;
+ m_isxtra = true;
+
+ if (m_current.hasNext()) {
+ ret = m_current.next();
+ }
+ }
+ // experimental tail optimisation
+ if (m_current instanceof ITailOp) {
+ m_current = ((ITailOp) m_current).availableTailOp();
+ }
+
+ return ret;
+ }
- //-------------------------------------------------------------
- // must call hasNext() to ensure m_current is correct
- public Object next() {
- if (hasNext()) {
- return m_current.next();
- }
+ public Iterator availableTailOp() {
+ if (m_isxtra) {
+ return m_current;
+ } else {
+ return this;
+ }
+ }
- throw new NoSuchElementException("Appenderator");
- }
+ // -------------------------------------------------------------
- //-------------------------------------------------------------
-
- public void remove() {
- m_current.remove();
- }
+ public void remove() {
+ m_current.remove();
+ }
}
\ No newline at end of file
Modified: branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Contractorator.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Contractorator.java 2011-02-24 01:04:12 UTC (rev 4236)
+++ branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Contractorator.java 2011-02-24 09:10:56 UTC (rev 4237)
@@ -42,12 +42,10 @@
*
* @author Martyn Cutcher
*/
-public class Contractorator implements Iterator {
+public class Contractorator extends Prefetch {
private final Iterator m_src;
protected final Object m_ctx;
private final Contractor m_contractor;
- private Object m_next;
- private boolean m_init = false;
public Contractorator(Iterator src, final Object ctx, Contractor contractor) {
m_src = src;
@@ -55,30 +53,14 @@
m_contractor = contractor;
}
- private void init() {
- if (!m_init) {
- m_next = m_contractor.contract(m_src);
- m_init = true;
+ protected Object getNext() {
+ if (m_src.hasNext()) {
+ return m_contractor.contract(m_src);
+ } else {
+ return null;
}
}
- public boolean hasNext() {
- init();
-
- return m_next != null;
- }
-
- public Object next() {
- if (!hasNext()) {
- throw new NoSuchElementException();
- }
-
- Object ret = m_next;
- m_next = m_contractor.contract(m_src);
-
- return ret;
- }
-
public void remove() {
throw new UnsupportedOperationException();
}
Modified: branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Expanderator.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Expanderator.java 2011-02-24 01:04:12 UTC (rev 4236)
+++ branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Expanderator.java 2011-02-24 09:10:56 UTC (rev 4237)
@@ -1,82 +1,55 @@
-/*
-Striterator - transformation and mapping patterns over java Iterators
+package cutthecrap.utils.striterators;
-Copyright (C) SYSTAP, LLC 2010. All rights reserved.
+import java.util.Iterator;
+import java.util.NoSuchElementException;
-Contact:
- SYSTAP, LLC
- 4501 Tower Road
- Greensboro, NC 27410
- lic...@bi...
+import cutthecrap.utils.striterators.IStriterator.ITailOp;
-This program is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; version 2 of the License.
+public class Expanderator extends Prefetch implements ITailOp {
-This program is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
+ private final Iterator m_src;
+ private Iterator m_child = null;
+ protected final Object m_context;
+ private final Expander m_expander;
-You should have received a copy of the GNU General Public License
-along with this program; if not, write to the Free Software
-Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
-*/
+ public Expanderator(Iterator src, Object context, Expander expander) {
+ m_src = src;
+ m_context = context;
+ m_expander = expander;
+ }
-package cutthecrap.utils.striterators;
+ // -------------------------------------------------------------
-import java.util.*;
+ protected Object getNext() {
+ if (m_child != null && m_child.hasNext()) {
+ final Object ret = m_child.next();
+
+ // experimental tail optimisation
+ if (m_child instanceof ITailOp) {
+ m_child = ((ITailOp) m_child).availableTailOp();
+ }
-/**
- * Expanderator
- *
- * Flattens out a two-level iteration. By combining Expanderators recursively a general tree
- * iteration is provided.
- *
- * Provides resolution for both the child object and also the nested iterator.
- * The actual expansion is via an Expander object that is passed in at construction.
- */
+ return ret;
+ } else if (m_src.hasNext()) {
+ m_child = m_expander.expand(m_src.next());
-public class Expanderator implements Iterator {
+ return getNext();
+ } else {
+ return null;
+ }
+ }
- private final Iterator m_src;
- private Iterator m_child = null;
- protected final Object m_context;
- private final Expander m_expander;
-
- public Expanderator(Iterator src, Object context, Expander expander) {
- m_src = src;
- m_context = context;
- m_expander = expander;
- }
+ // -------------------------------------------------------------
- //-------------------------------------------------------------
-
- public boolean hasNext() {
- if (m_child != null && m_child.hasNext()) {
- return true;
- } else if (m_src.hasNext()) {
- m_child = m_expander.expand(m_src.next());
-
- return hasNext();
- } else {
- return false;
- }
- }
-
- //-------------------------------------------------------------
- // must call hasNext() to ensure m_child is setup
- public Object next() {
- if (hasNext()) {
- return m_child.next();
- }
-
- throw new NoSuchElementException("Expanderator");
- }
-
- //-------------------------------------------------------------
-
- public void remove() {
- m_child.remove();
- }
-}
\ No newline at end of file
+ public void remove() {
+ m_child.remove();
+ }
+
+ public Iterator availableTailOp() {
+ if ((!ready()) && !m_src.hasNext()) {
+ return m_child;
+ } else {
+ return this;
+ }
+ }
+}
Modified: branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Filterator.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Filterator.java 2011-02-24 01:04:12 UTC (rev 4236)
+++ branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Filterator.java 2011-02-24 09:10:56 UTC (rev 4237)
@@ -41,20 +41,10 @@
* <p>The Filterator provide the protocol support to utilize Filter objects.</p>
*/
-public class Filterator implements Iterator {
+public class Filterator extends Prefetch {
final private Iterator m_src;
- /**
- * Flag set once {@link #getNext()} is invoked at least once.
- */
- private boolean didInit = false;
-
- /**
- * Pre-fetched, but initial prefetch must not be done in the constructor.
- */
- private Object m_value = null;
-
final protected Object m_context;
final protected Filter m_filter;
@@ -62,38 +52,11 @@
m_src = src;
m_context = context;
m_filter = filter;
-
- /*
- * Note: eager initialization causes problems when we are stacking
- * filters.
- */
-// m_value = getNext();
}
- //-------------------------------------------------------------
- public boolean hasNext() {
- if (!didInit) {
- m_value = getNext();
- }
- return m_value != null;
- }
-
//-------------------------------------------------------------
- // must call hasNext() to ensure m_child is setup
- public Object next() {
- if (hasNext()) {
- Object val = m_value;
- m_value = getNext();
- return val;
- }
-
- throw new NoSuchElementException("FilterIterator");
- }
-
- //-------------------------------------------------------------
-
public void remove() {
m_src.remove();
}
@@ -101,7 +64,6 @@
//-------------------------------------------------------------
protected Object getNext() {
- didInit = true;
while (m_src.hasNext()) {
final Object next = m_src.next();
Modified: branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/IStriterator.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/IStriterator.java 2011-02-24 01:04:12 UTC (rev 4236)
+++ branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/IStriterator.java 2011-02-24 09:10:56 UTC (rev 4237)
@@ -59,4 +59,16 @@
* iter.map(this, MyClass.aMethod);
**/
public IStriterator map(Object client, Method method);
+
+ public interface ITailOp {
+ /**
+ * Opportunity for a Striterator to provide a "tail iterator" to
+ * shorten the call stack. For example, an Appenderator would return
+ * the second iterator if current. Or an Expanderator the child iterator
+ * if there were no more source objects.
+ *
+ * @return a tail optimizing iterator if possible
+ */
+ public Iterator availableTailOp();
+ }
}
Added: branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Prefetch.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Prefetch.java (rev 0)
+++ branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Prefetch.java 2011-02-24 09:10:56 UTC (rev 4237)
@@ -0,0 +1,46 @@
+package cutthecrap.utils.striterators;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+public abstract class Prefetch implements Iterator {
+ private Object m_next;
+ private boolean m_ready = false;
+
+ final private void checkInit() {
+ if (!m_ready) {
+ m_next = getNext();
+ m_ready = true;
+ }
+ }
+
+ abstract protected Object getNext();
+
+ public boolean hasNext() {
+ checkInit();
+
+ return m_next != null;
+ }
+
+ public Object next() {
+ checkInit(); // check prefetch is ready
+
+ if (m_next == null) {
+ throw new NoSuchElementException();
+ }
+
+ Object ret = m_next;
+
+ // do not prefetch on next() since this may cause problems with
+ // side-effecting
+ // overides
+ m_next = null;
+ m_ready = false;
+
+ return ret;
+ }
+
+ protected boolean ready() {
+ return m_ready;
+ }
+}
Property changes on: branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Prefetch.java
___________________________________________________________________
Added: svn:mime-type
+ text/plain
Added: svn:keywords
+ Id Date Revision Author HeadURL
Modified: branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Striterator.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Striterator.java 2011-02-24 01:04:12 UTC (rev 4236)
+++ branches/QUADS_QUERY_BRANCH/ctc-striterators/src/java/cutthecrap/utils/striterators/Striterator.java 2011-02-24 09:10:56 UTC (rev 4237)
@@ -32,6 +32,8 @@
import java.util.LinkedList;
import java.util.List;
+import cutthecrap.utils.striterators.IStriterator.ITailOp;
+
/**
* Striterator
*
@@ -40,7 +42,7 @@
* The IFilter objects passed to addFilter allow selection criteria for the iterated objects.
* The <code>addTypeFilter</code> method allows easy specification of a class type restriction.
*/
-public class Striterator implements IStriterator {
+public class Striterator implements IStriterator, ITailOp {
volatile List<IFilter> filters = null; // Note: NOT serializable.
private volatile Iterator realSource;
private volatile Iterator m_src = null;
@@ -82,7 +84,13 @@
public Object next() {
if (m_src == null)
compile(realSource);
- return m_src.next();
+ final Object ret = m_src.next();
+ // experimental tail optimisation
+ if (m_src instanceof ITailOp) {
+ Object old = m_src;
+ m_src = ((ITailOp) m_src).availableTailOp();
+ }
+ return ret;
}
/** Enumeration version of hasNext() **/
@@ -120,7 +128,7 @@
return this;
}
-
+
public void compile(final Iterator src) {
compile(src, null/* context */);
}
@@ -190,4 +198,27 @@
return sb.toString();
}
+ /**
+ * If this Striterator has not been overriden then return the
+ * source iterator, or even better, try and recurse to the nested tailOp
+ * if available.
+ *
+ * This has been disabled since it appears to have a negative effect.
+ *
+ * To reactivate, uncomment the ITailOp implementation declaration.
+ *
+ * TODO: Investigate apparent performance degradation with activation
+ *
+ * @return
+ */
+ boolean doneone = false;
+ public Iterator availableTailOp() {
+ final boolean avail = Striterator.class == this.getClass();
+
+ if (avail) {
+ return (m_src instanceof ITailOp) ? ((ITailOp) m_src).availableTailOp() : m_src;
+ } else {
+ return this;
+ }
+ }
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
