<< Back to previous view

[CRRBV-2] Efficient reverse resulting in reversed rrb-vector Created: 20/Dec/13  Updated: 20/Dec/13

Status: Open
Project: core.rrb-vector
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Major
Reporter: Gunnar Völkel Assignee: Michał Marczyk
Resolution: Unresolved Votes: 0
Labels: enhancement


 Description   

Is it possible to implement an efficient reverse on a rrb-vector resulting in an rrb-vector? This would be pretty useful in scenarios like the 2-opt neighborhood for local search for the Traveling Salesman Problem. The complete operation is as follows.

Given: a = [a_0, a_1, ..., a_{n-1}, a_{n}, a_{n+1}, ..., a_{n+k-2}, a_{n+k-1}, a_{n+k}, ..., a_{n+k+m-1}]
Goal: [a_0, a_1, ..., a_{n-1}, a_{n+k-1}, a_{n+k-2}, ..., a_{n+1}, a_{n}, a_{n+k}, ..., a_{n+k+m-1}]

Possible Clojure implementation of the described operation:

(let [x (subvec a 0 n), y (subvec a n (+ n k)), z (subvec a (+ n k))]
 (catvec x, (reverse-vec y), z))





[CRRBV-9] Repeated subvec and catvec fails Created: 17/Mar/15  Updated: 25/Mar/15

Status: Open
Project: core.rrb-vector
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Neil Kirsopp Assignee: Michał Marczyk
Resolution: Unresolved Votes: 0
Labels: None

Attachments: Text File subvec-catvec-2.patch     Text File subvec-catvec.patch    
Patch: Code and Test

 Description   

The attached patch contains a test which fails for both the Clojure and ClojureScript implementations. It simply repeatedly calls subvec and catvec to assemble an interleaved vector. The patch attached contains fixes for Clojure only. I will investigate the fixes for CLJS, but thought it best to raise an issue with my findings so far.

2371 is the minimum length that exhibits the behaviour (triggers an ArrayIndexOutOfBoundsException).



 Comments   
Comment by Neil Kirsopp [ 17/Mar/15 10:45 AM ]

New patch passing tests in Clojure and ClojureScript.

Comment by Michał Marczyk [ 25/Mar/15 8:30 PM ]

Thanks so much once again! I've applied your patch to master and added a test.check-based version of your test-reduce-subvec-catvec test (keeping the original breaking example).





[CRRBV-10] Calling empty in CLJS results in a PersistentVector Created: 01/Jul/15  Updated: 01/Jul/15

Status: Open
Project: core.rrb-vector
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Neil Kirsopp Assignee: Michał Marczyk
Resolution: Unresolved Votes: 0
Labels: None

Attachments: Text File empty-vec.patch    
Patch: Code and Test

 Description   

I discovered that (pop some-rrb-vec) where some-rrb-vec is of length 1 returns a PersistentVector rather than a clojure.core.rrbt.Vector in ClojureScript.

This isn't true for the Clojure side, so I assume it's a problem. Patch attached with tests.






[CRRBV-11] Issue with Clojure 1.8.0-alpha2 Tuples Created: 29/Jul/15  Updated: 29/Jul/15

Status: Open
Project: core.rrb-vector
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Mike Anderson Assignee: Michał Marczyk
Resolution: Unresolved Votes: 0
Labels: None


 Description   

When trying our core.rrb-vector with the latest Clojure 1.8.0-alpha2 I see the following error:

Exception in thread "main" java.lang.IllegalArgumentException: No implementation of method: :slicev of protocol: #'clojure.core.rrb-vector.protocols/PSliceableVector found for class: clojure.lang.Tuple$T0, compiling:(mikera/timeline/examples.clj:12:1)
at clojure.lang.Compiler.load(Compiler.java:7307)
at clojure.lang.RT.loadResourceScript(RT.java:372)
at clojure.lang.RT.loadResourceScript(RT.java:363)
at clojure.lang.RT.load(RT.java:453)
at clojure.lang.RT.load(RT.java:419)
at clojure.core$load$fn__5448.invoke(core.clj:5866)
at clojure.core$load.doInvoke(core.clj:5865)
at clojure.lang.RestFn.invoke(RestFn.java:408)
at clojure.core$load_one.invoke(core.clj:5671)
at clojure.core$load_lib$fn__5397.invoke(core.clj:5711)
at clojure.core$load_lib.doInvoke(core.clj:5710)
at clojure.lang.RestFn.applyTo(RestFn.java:142)
at clojure.core$apply.invoke(core.clj:632)
at clojure.core$load_libs.doInvoke(core.clj:5749)
at clojure.lang.RestFn.applyTo(RestFn.java:137)
at clojure.core$apply.invoke(core.clj:632)
at clojure.core$require.doInvoke(core.clj:5832)
at clojure.lang.RestFn.invoke(RestFn.java:408)
at com.theoryinpractise.clojure.testrunner$eval41$iter_4246$fn47$fn_48.invoke(run-test181131806783576232.clj:22)
at com.theoryinpractise.clojure.testrunner$eval41$iter_4246$fn_47.invoke(run-test181131806783576232.clj:21)
at clojure.lang.LazySeq.sval(LazySeq.java:40)
at clojure.lang.LazySeq.seq(LazySeq.java:49)
at clojure.lang.RT.seq(RT.java:514)
at clojure.core$seq__4128.invoke(core.clj:137)
at clojure.core$dorun.invoke(core.clj:3009)
at com.theoryinpractise.clojure.testrunner$eval41.invoke(run-test181131806783576232.clj:21)
at clojure.lang.Compiler.eval(Compiler.java:6850)
at clojure.lang.Compiler.load(Compiler.java:7295)
at clojure.lang.Compiler.loadFile(Compiler.java:7233)
at clojure.main$load_script.invoke(main.clj:275)
at clojure.main$script_opt.invoke(main.clj:337)
at clojure.main$main.doInvoke(main.clj:421)
at clojure.lang.RestFn.invoke(RestFn.java:421)
at clojure.lang.Var.invoke(Var.java:383)
at clojure.lang.AFn.applyToHelper(AFn.java:156)
at clojure.lang.Var.applyTo(Var.java:700)
at clojure.main.main(main.java:37)
Caused by: java.lang.IllegalArgumentException: No implementation of method: :slicev of protocol: #'clojure.core.rrb-vector.protocols/PSliceableVector found for class: clojure.lang.Tuple$T0
at clojure.core$_cache_protocol_fn.invoke(core_deftype.clj:556)
at clojure.core.rrb_vector.protocols$eval965$fn_966$G956_975.invoke(protocols.clj:6)
at clojure.core.rrb_vector$subvec.invoke(rrb_vector.clj:71)
at mikera.timeline.impl.Timeline.add_event(impl.clj:82)
at mikera.timeline$log.invoke(timeline.clj:64)
at mikera.timeline$log.invoke(timeline.clj:61)
at clojure.lang.Atom.swap(Atom.java:51)
at clojure.core$swap_BANG_.invoke(core.clj:2239)
at mikera.timeline.examples$eval1620.invoke(examples.clj:15)
at clojure.lang.Compiler.eval(Compiler.java:6850)
at clojure.lang.Compiler.load(Compiler.java:7295)
... 36 more

I believe the cause of this is the new Tuple types. core-rrb-vector should ideally be able to handle this like any other IPersistentVector instance, but it does not currently seem to be able to do so.






[CRRBV-12] ClassCastException: clojure.lang.PersistentVector$Node cannot be cast to [I Created: 30/Aug/15  Updated: 30/Aug/15

Status: Open
Project: core.rrb-vector
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Jonas Enlund Assignee: Michał Marczyk
Resolution: Unresolved Votes: 0
Labels: None
Environment:

core.rrb-vector version 0.0.11 and clojure version 1.7.0


Attachments: File failing-1193.edn    

 Description   

I'm seeing some strange behaviour which I've been unable to find a small failing case for.

(defn quicksort [v]
  (if (<= (count v) 1)
    v
    (let [[x & xs] v]
      (rrb/catvec (quicksort (filterv #(<= % x) xs)) 
                  [x]
                  (quicksort (filterv #(> % x) xs))))))

We can check this implementation with test.check

(defn ascending? [coll]
  (every? (fn [[a b]] (<= a b))
          (partition 2 1 coll)))

(def property
  (prop/for-all [v (gen/vector gen/int)]
    (let [s (quicksort v)]
      (and (= (count v) (count s))
           (ascending? s)))))

(tc/quick-check 10000 property)

;; => {:result true, :num-tests 10000, :seed 1440948212354}

(I've bumped the number of checks to 1e6 but test.check was not able to find a failing case)

Still, for some reason I get a "ClassCastException: clojure.lang.PersistentVector$Node cannot be cast to [I" for the attached 1193 element vector.

code
(quicksort (read-string (slurp "failing-1193.edn")))
code



 Comments   
Comment by Jonas Enlund [ 30/Aug/15 12:12 PM ]

The expression

(quicksort (shuffle (range 1e6)))

1. succeeds (~20%)
2. throws ArrayIndexOutOfBoundsException (~20%)

#error {
 :cause "33"
 :via
 [{:type java.lang.ArrayIndexOutOfBoundsException
   :message "33"
   :at [clojure.core.rrb_vector.rrbt.Vector$fn__3827 invoke "rrbt.clj" 621]}]
 :trace
 [[clojure.core.rrb_vector.rrbt.Vector$fn__3827 invoke "rrbt.clj" 621]
  [clojure.core.rrb_vector.rrbt.Vector arrayFor "rrbt.clj" 620]
  [clojure.core.rrb_vector.rrbt.VecSeq chunkedNext "rrbt.clj" 111]
  [clojure.core.rrb_vector.rrbt.VecSeq next "rrbt.clj" 74]
  [clojure.lang.RT next "RT.java" 674]
  [clojure.core$next__4112 invoke "core.clj" 64]
  [clojure.core$nthnext invoke "core.clj" 3038]
  [clojure.core$print_sequential invoke "core_print.clj" 49]
  [clojure.core$fn__5859 invoke "core_print.clj" 206]
  [clojure.lang.MultiFn invoke "MultiFn.java" 233]
  [clojure.tools.nrepl.middleware.pr_values$pr_values$fn$reify__600 send "pr_values.clj" 35]
  [sun.reflect.GeneratedMethodAccessor13 invoke nil -1]
  [sun.reflect.DelegatingMethodAccessorImpl invoke "DelegatingMethodAccessorImpl.java" 43]
  [java.lang.reflect.Method invoke "Method.java" 606]
  [clojure.lang.Reflector invokeMatchingMethod "Reflector.java" 93]
  [clojure.lang.Reflector invokeInstanceMethod "Reflector.java" 28]
  [clojure.tools.nrepl.middleware.load_file$wrap_load_file$fn$reify__787 send "load_file.clj" 93]
  [clojure.tools.nrepl.middleware.interruptible_eval$evaluate$fn__623$fn__634 invoke "interruptible_eval.clj" 82]
  [clojure.main$repl$read_eval_print__7099 invoke "main.clj" 241]
  [clojure.main$repl$fn__7108 invoke "main.clj" 258]
  [clojure.main$repl doInvoke "main.clj" 258]
  [clojure.lang.RestFn invoke "RestFn.java" 1523]
  [clojure.tools.nrepl.middleware.interruptible_eval$evaluate$fn__623 invoke "interruptible_eval.clj" 58]
  [clojure.lang.AFn applyToHelper "AFn.java" 152]
  [clojure.lang.AFn applyTo "AFn.java" 144]
  [clojure.core$apply invoke "core.clj" 630]
  [clojure.core$with_bindings_STAR_ doInvoke "core.clj" 1868]
  [clojure.lang.RestFn invoke "RestFn.java" 425]
  [clojure.tools.nrepl.middleware.interruptible_eval$evaluate invoke "interruptible_eval.clj" 56]
  [clojure.tools.nrepl.middleware.interruptible_eval$interruptible_eval$fn__665$fn__668 invoke "interruptible_eval.clj" 191]
  [clojure.tools.nrepl.middleware.interruptible_eval$run_next$fn__660 invoke "interruptible_eval.clj" 159]
  [clojure.lang.AFn run "AFn.java" 22]
  [java.util.concurrent.ThreadPoolExecutor runWorker "ThreadPoolExecutor.java" 1145]
  [java.util.concurrent.ThreadPoolExecutor$Worker run "ThreadPoolExecutor.java" 615]
  [java.lang.Thread run "Thread.java" 745]]}

3. Throws the above mentioned ClassCastException (~60%)

#error {
 :cause "clojure.lang.PersistentVector$Node cannot be cast to [I"
 :via
 [{:type clojure.lang.Compiler$CompilerException
   :message "java.lang.ClassCastException: clojure.lang.PersistentVector$Node cannot be cast to [I, compiling:(/Users/jonasenlund/dev/clojure/the-other-datastructures/src/the_other_datastructures/rrb.clj:221:1)"
   :at [clojure.lang.Compiler load "Compiler.java" 7239]}
  {:type java.lang.ClassCastException
   :message "clojure.lang.PersistentVector$Node cannot be cast to [I"
   :at [clojure.lang.Numbers ints "Numbers.java" 1396]}]
 :trace
 [[clojure.lang.Numbers ints "Numbers.java" 1396]
  [clojure.core.rrb_vector.nodes$fold_tail invoke "nodes.clj" 265]
  [clojure.core.rrb_vector.nodes$fold_tail invoke "nodes.clj" 268]
  [clojure.core.rrb_vector.rrbt$splice_rrbts invoke "rrbt.clj" 1357]
  [clojure.core.rrb_vector.rrbt.Vector splicev "rrbt.clj" 928]
  [clojure.core.rrb_vector$catvec invoke "rrb_vector.clj" 54]
  [the_other_datastructures.rrb$eval4682$quicksort__4683 invoke "rrb.clj" 217]
  [the_other_datastructures.rrb$eval4682$quicksort__4683 invoke "rrb.clj" 217]
  [the_other_datastructures.rrb$eval4682$quicksort__4683 invoke "rrb.clj" 217]
  [the_other_datastructures.rrb$eval4682$quicksort__4683 invoke "rrb.clj" 219]
  [the_other_datastructures.rrb$eval4682$quicksort__4683 invoke "rrb.clj" 217]
  [the_other_datastructures.rrb$eval4682$quicksort__4683 invoke "rrb.clj" 219]
  [the_other_datastructures.rrb$eval4682$quicksort__4683 invoke "rrb.clj" 219]
  [the_other_datastructures.rrb$eval4682$quicksort__4683 invoke "rrb.clj" 217]
  [the_other_datastructures.rrb$eval4682$quicksort__4683 invoke "rrb.clj" 217]
  [the_other_datastructures.rrb$eval4682$quicksort__4683 invoke "rrb.clj" 217]
  [the_other_datastructures.rrb$eval4682$quicksort__4683 invoke "rrb.clj" 219]
  [the_other_datastructures.rrb$eval4682$quicksort__4683 invoke "rrb.clj" 217]
  [the_other_datastructures.rrb$eval4921 invoke "rrb.clj" 221]
  [clojure.lang.Compiler eval "Compiler.java" 6782]
  [clojure.lang.Compiler load "Compiler.java" 7227]
  [user$eval4909 invoke "form-init3543508351311666483.clj" 1]
  [clojure.lang.Compiler eval "Compiler.java" 6782]
  [clojure.lang.Compiler eval "Compiler.java" 6745]
  [clojure.core$eval invoke "core.clj" 3081]
  [clojure.main$repl$read_eval_print__7099$fn__7102 invoke "main.clj" 240]
  [clojure.main$repl$read_eval_print__7099 invoke "main.clj" 240]
  [clojure.main$repl$fn__7108 invoke "main.clj" 258]
  [clojure.main$repl doInvoke "main.clj" 258]
  [clojure.lang.RestFn invoke "RestFn.java" 1523]
  [clojure.tools.nrepl.middleware.interruptible_eval$evaluate$fn__623 invoke "interruptible_eval.clj" 58]
  [clojure.lang.AFn applyToHelper "AFn.java" 152]
  [clojure.lang.AFn applyTo "AFn.java" 144]
  [clojure.core$apply invoke "core.clj" 630]
  [clojure.core$with_bindings_STAR_ doInvoke "core.clj" 1868]
  [clojure.lang.RestFn invoke "RestFn.java" 425]
  [clojure.tools.nrepl.middleware.interruptible_eval$evaluate invoke "interruptible_eval.clj" 56]
  [clojure.tools.nrepl.middleware.interruptible_eval$interruptible_eval$fn__665$fn__668 invoke "interruptible_eval.clj" 191]
  [clojure.tools.nrepl.middleware.interruptible_eval$run_next$fn__660 invoke "interruptible_eval.clj" 159]
  [clojure.lang.AFn run "AFn.java" 22]
  [java.util.concurrent.ThreadPoolExecutor runWorker "ThreadPoolExecutor.java" 1145]
  [java.util.concurrent.ThreadPoolExecutor$Worker run "ThreadPoolExecutor.java" 615]
  [java.lang.Thread run "Thread.java" 745]]}




Generated at Fri Sep 04 09:37:43 CDT 2015 using JIRA 4.4#649-r158309.