[libgee] Specialise the stream iterator
- From: Maciej Marcin Piechotka <mpiechotka src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [libgee] Specialise the stream iterator
- Date: Sat, 6 Jul 2013 17:55:18 +0000 (UTC)
commit c1e39f58c360d6ac1b8522234361108bdce5475f
Author: Maciej Piechotka <uzytkownik2 gmail com>
Date: Sat Jul 6 19:43:01 2013 +0200
Specialise the stream iterator
In the test this improves running time by 4%-22% depending on test.
On 1048575 elements:
- Calling filter and iterating: 1.006±0.008 → 0.80±0.02
- Calling map and iterating: 1.65±0.03 → 1.441±0.005
- Calling flat_map and iterating: 11.12±0.09 → 10.69±0.01
gee/Makefile.am | 1 +
gee/streamiterator.vala | 165 +++++++++++++++++++++++++++++++++++++++++++++++
gee/traversable.vala | 64 +-----------------
3 files changed, 169 insertions(+), 61 deletions(-)
---
diff --git a/gee/Makefile.am b/gee/Makefile.am
index 115920f..1f9a2b8 100644
--- a/gee/Makefile.am
+++ b/gee/Makefile.am
@@ -68,6 +68,7 @@ libgee_0_8_la_SOURCES = \
set.vala \
sortedmap.vala \
sortedset.vala \
+ streamiterator.vala \
task.vala \
timsort.vala \
traversable.vala \
diff --git a/gee/streamiterator.vala b/gee/streamiterator.vala
new file mode 100644
index 0000000..701f2e1
--- /dev/null
+++ b/gee/streamiterator.vala
@@ -0,0 +1,165 @@
+/* streamiterator.vala
+ *
+ * Copyright (C) 2011-2012 Maciej Piechotka
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library 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
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Author:
+ * Maciej Piechotka <uzytkownik2 gmail com>
+ */
+
+internal class Gee.StreamIterator<A, G> : GLib.Object, Traversable<A>, Iterator<A> {
+ public StreamIterator (Iterator<G> outer, owned StreamFunc<A, G> func) {
+ _outer = outer;
+ _func = (owned)func;
+ _current = null;
+ _need_next = true;
+ _finished = false;
+
+ _state = _func (Traversable.Stream.YIELD, null, out _current);
+ switch (_state) {
+ case Traversable.Stream.WAIT:
+ case Traversable.Stream.YIELD:
+ _need_next = !_outer.valid;
+ break;
+ case Traversable.Stream.CONTINUE:
+ if (_outer.valid) {
+ _state = _func (_state, new Lazy<G> (() => {return _outer.get ();}), out
_current);
+ switch (_state) {
+ case Traversable.Stream.YIELD:
+ case Traversable.Stream.CONTINUE:
+ case Traversable.Stream.WAIT:
+ break;
+ case Traversable.Stream.END:
+ _finished = true;
+ return;
+ default:
+ assert_not_reached ();
+ }
+ }
+ break;
+ case Traversable.Stream.END:
+ _finished = true;
+ return;
+ }
+ }
+
+ public bool foreach (ForallFunc<A> f) {
+ Lazy<G>? current = null;
+ if (_current != null) {
+ if (!f (_current.value)) {
+ return false;
+ }
+ }
+ if (_next != null) {
+ current = (owned)_next;
+ if (!f (current.value)) {
+ return false;
+ }
+ } else if (_finished) {
+ return true;
+ }
+ unowned Iterator<G> outer = _outer;
+ StreamFunc<A, G> func = _func;
+ Traversable.Stream state = _state;
+ bool need_next = _need_next;
+ bool result = true;
+ Lazy<G>? next_current;
+ while ((next_current = yield_next<A, G>(outer, func, ref state, ref need_next)) != null) {
+ current = (owned)next_current;
+ if (!f (current.value)) {
+ result = false;
+ break;
+ }
+ }
+ _state = state;
+ _need_next = need_next;
+ _finished = result;
+ _current = (owned)current;
+ return result;
+ }
+
+ public bool next () {
+ if (has_next ()) {
+ _current = (owned)_next;
+ return true;
+ } else {
+ return false;
+ }
+ }
+
+ public bool has_next () {
+ if (_finished) {
+ return false;
+ }
+ if (_next != null) {
+ return true;
+ }
+ _next = yield_next<A, G> (_outer, _func, ref _state, ref _need_next);
+ _finished = _next == null;
+ return !_finished;
+ }
+
+ public new A get () {
+ assert (_current != null);
+ return _current.value;
+ }
+
+ public void remove () {
+ assert_not_reached ();
+ }
+
+ public bool valid { get { return _current != null; } }
+ public bool read_only { get { return true; } }
+
+ private static inline Lazy<A>? yield_next<A, G> (Iterator<G> outer, StreamFunc<A, G> func, ref
Traversable.Stream state, ref bool need_next) {
+ Lazy<A>? value = null;
+ if (state != Traversable.Stream.CONTINUE)
+ state = func (state, null, out value);
+ while (true) {
+ switch (state) {
+ case Traversable.Stream.YIELD:
+ return value;
+ case Traversable.Stream.CONTINUE:
+ if (need_next) {
+ if (!outer.next ()) {
+ state = func (Traversable.Stream.END, null, out value);
+ continue;
+ }
+ } else {
+ need_next = true;
+ }
+ state = func (state, new Lazy<G> (() => {return outer.get ();}), out value);
+ break;
+ case Traversable.Stream.WAIT:
+ state = func (state, null, out value);
+ break;
+ case Traversable.Stream.END:
+ return null;
+ default:
+ assert_not_reached ();
+ }
+ }
+ }
+
+ private Iterator<G> _outer;
+ private StreamFunc<A, G> _func;
+ private Lazy<A>? _current;
+ private Lazy<A>? _next;
+ private Traversable.Stream _state;
+ private bool _need_next;
+ private bool _finished;
+}
+
diff --git a/gee/traversable.vala b/gee/traversable.vala
index 0ab1b52..4c514fc 100644
--- a/gee/traversable.vala
+++ b/gee/traversable.vala
@@ -109,69 +109,11 @@ public interface Gee.Traversable<G> : Object {
* @return iterator containing values yielded by stream
*/
public virtual Iterator<A> stream<A> (owned StreamFunc<G, A> f) {
- Iterator<G>? self;
- Iterable<G>? iself;
+ unowned Iterator<G>? self;
+ unowned Iterable<G>? iself;
// Yes - I've heard of polimorphism ;) but I don't want users to need to implement the method.
if ((self = this as Iterator<G>) != null) {
- Traversable.Stream str;
- Lazy<A>? initial = null;
- bool need_next = true;
- str = f (Stream.YIELD, null, out initial);
- switch (str) {
- case Stream.WAIT:
- case Stream.YIELD:
- if (self.valid)
- need_next = false;
- break;
- case Stream.CONTINUE:
- if (self.valid) {
- str = f (Stream.CONTINUE, new Lazy<G> (() => {return self.get ();}),
out initial);
- switch (str) {
- case Stream.YIELD:
- case Stream.CONTINUE:
- case Stream.WAIT:
- break;
- case Stream.END:
- return Iterator.unfold<A> (() => {return null;});
- default:
- assert_not_reached ();
- }
- }
- break;
- case Stream.END:
- return Iterator.unfold<A> (() => {return null;});
- default:
- assert_not_reached ();
- }
- return Iterator.unfold<A> (() => {
- Lazy<A>? val = null;
- if (str != Stream.CONTINUE)
- str = f (str, null, out val);
- while (true) {
- switch (str) {
- case Stream.YIELD:
- return val;
- case Stream.CONTINUE:
- if (need_next) {
- if (!self.next ()) {
- str = f (Traversable.Stream.END, null, out
val);
- continue;
- }
- } else {
- need_next = true;
- }
- str = f (Stream.CONTINUE, new Lazy<G> (() => {return self.get
();}), out val);
- break;
- case Stream.WAIT:
- str = f (Stream.WAIT, null, out val);
- break;
- case Stream.END:
- return null;
- default:
- assert_not_reached ();
- }
- }
- }, initial);
+ return new StreamIterator<A, G> (self, (owned)f);
} else if ((iself = this as Iterable<G>) != null) {
return iself.iterator().stream<A> ((owned) f);
} else {
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
