Returning iterators instead of Vec

help
1

I have a function (fn move) that returns a Vec of structs (Vec).
It does so by calling sub functions that also return Vec and
concateneting the results.

I want the sub functions to return iterators instead and collect them
into a Vec in fn move.

Based on a simpler case I think the return type of the sub functions needs to be something like
Box<dyn Iterator<Item = Move>>
but doesn't work here - get into a cycle with the compiler suggesting add + '_ trait or add another dyn only to suggest try removing them again...

Original source is here (that version compiles ok).

2

What happens with abstract return types? I.e. impl Iterator<Item = Move>.

1 Like
3

Wish that worked - and it does if there is only one sub function - however there are several here and each has a different type (computed from different closures) - even though they collect into Vec . Box is a way around that.

4

Here's where you collect the different iterators and flatten them, is that correct?

Indeed the match statement in line 100 would be problematic with abstract return types. But I don't get why trait objects don't work. Maybe it has something to do with the interface of itertoos::concat. Try using the flatten method instead, please. I.e. something like this:

fn iter1() -> Box<dyn Iterator<Item = u8>> {
    Box::new(vec![0, 1, 2].into_iter().map(|x| x + 1))
}

fn iter2() -> Box<dyn Iterator<Item = u8>> {
    Box::new(vec![3, 4, 5].into_iter().filter(|x| x % 2 == 1))
}

fn main() {
    let v: Vec<u8> = (0..2)
        .map(|x| match x {
            0 => iter1(),
            1 => iter2(),
            _ => unreachable!(),
        })
        .flatten()
        .collect();

    assert_eq!(v, vec![1, 2, 3, 3, 5]);
}

Playground.

(or flat_map, like you did before opting for itertools::concat)

1 Like
5

Hmm. Parallel implemntations in python3 and rust - see their respective folders.

So your goal is to create extra-slow and extra-memory-hungry Python-in-Rust code. If that's true then why wouldn't you just wrap everything in Rc<RefCell<…>>?

That's usually the best approximation for the Python-in-Rust (even if you would, probably need iterators which keep Rc inside).

If the goal is, indeed, to write Python-In-Rust code then most ideomatic crates would complain about your design decisions.

You would need the whole set of Python-like modules or crates to emulate Python in Rust with sufficient flexibility (and appropriate inefficiency).

6

The trait object vs. impl Trait (i.e., dynamic vs. static existential) is a red herring. Your problem is that you are using .iter() where you actually need .into_iter() (which would return a reference to a local), and you are trying to use lifetime elision in the return type when there are more than one reference parameters (in which case the compiler simply can't figure out which argument to tie the return type to).

Here's the correct diff:

diff --git a/rs/src/mgen.rs b/rs/src/mgen.rs
index a584098..94af17e 100644
--- a/rs/src/mgen.rs
+++ b/rs/src/mgen.rs
@@ -90,29 +90,26 @@ pub fn moves(
     };
     let bm_board = bm_white | bm_black;
 
-    // concat faster than flat_map collect
-    itertools::concat(
-        board
-            .iter()
-            .enumerate()
-            .filter(|(_, &p)| p != NIL && p.colour == colour)
-            //.flat_map(|(frm, &p)| match p {
-            .map(|(frm, &p)| match p {
-                N1 | N2 => knight_moves(board, frm, bm_own),
-                K1 | K2 => king_moves(board, frm, bm_own, bm_board, end_game, can_castle, colour),
-                P1 | P2 => pawn_moves(board, frm, last, bm_opp, bm_board, colour),
-                R1 | R2 => ray_moves(board, frm, BM_ROOK_MOVES[frm], bm_board, bm_own),
-                B1 | B2 => ray_moves(board, frm, BM_BISHOP_MOVES[frm], bm_board, bm_own),
-                Q1 | Q2 => ray_moves(board, frm, BM_QUEEN_MOVES[frm], bm_board, bm_own),
-                _ => Vec::new(),
-            }), //.collect()
-    )
+    board
+        .iter()
+        .enumerate()
+        .filter(|(_, &p)| p != NIL && p.colour == colour)
+        .flat_map(|(frm, &p)| match p {
+            N1 | N2 => knight_moves(board, frm, bm_own),
+            K1 | K2 => king_moves(board, frm, bm_own, bm_board, end_game, can_castle, colour),
+            P1 | P2 => pawn_moves(board, frm, last, bm_opp, bm_board, colour),
+            R1 | R2 => ray_moves(board, frm, BM_ROOK_MOVES[frm], bm_board, bm_own),
+            B1 | B2 => ray_moves(board, frm, BM_BISHOP_MOVES[frm], bm_board, bm_own),
+            Q1 | Q2 => ray_moves(board, frm, BM_QUEEN_MOVES[frm], bm_board, bm_own),
+            _ => Box::new(core::iter::empty()),
+        })
+        .collect()
 }
 
-fn knight_moves(board: &[Piece; 64], frm: usize, bm_own: u64) -> Vec<Move> {
-    bm2vec(BM_KNIGHT_MOVES[frm] & !bm_own)
-        .iter()
-        .map(|&to| Move {
+fn knight_moves(board: &[Piece; 64], frm: usize, bm_own: u64) -> Box<dyn Iterator<Item = Move> + '_> {
+    Box::new(bm2vec(BM_KNIGHT_MOVES[frm] & !bm_own)
+        .into_iter()
+        .map(move |to| Move {
             frm,
             to,
             castle: false,
@@ -120,17 +117,16 @@ fn knight_moves(board: &[Piece; 64], frm: usize, bm_own: u64) -> Vec<Move> {
             kill: (board[to], to),
             val: pval(board[frm], to) - pval(board[frm], frm) - pval(board[to], to),
             hash: phashkey(board[frm], to) ^ phashkey(board[frm], frm) ^ phashkey(board[to], to),
-        })
-        .collect::<Vec<Move>>()
+        }))
 }
 
-fn ray_moves(board: &[Piece; 64], frm: usize, moves: u64, bm_board: u64, bm_own: u64) -> Vec<Move> {
+fn ray_moves(board: &[Piece; 64], frm: usize, moves: u64, bm_board: u64, bm_own: u64) -> Box<dyn Iterator<Item = Move> + '_> {
     let bl: u64 = bm2vec(moves & bm_board)
         .iter()
         .fold(0, |a, i| a | BM_BLOCKED[frm][*i]);
-    bm2vec(moves & !bl & !bm_own)
-        .iter()
-        .map(|&to| Move {
+    Box::new(bm2vec(moves & !bl & !bm_own)
+        .into_iter()
+        .map(move |to| Move {
             frm,
             to,
             castle: false,
@@ -138,19 +134,18 @@ fn ray_moves(board: &[Piece; 64], frm: usize, moves: u64, bm_board: u64, bm_own:
             kill: (board[to], to),
             val: pval(board[frm], to) - pval(board[frm], frm) - pval(board[to], to),
             hash: phashkey(board[frm], to) ^ phashkey(board[frm], frm) ^ phashkey(board[to], to),
-        })
-        .collect::<Vec<Move>>()
+        }))
 }
 
-fn pawn_moves(
-    board: &[Piece; 64],
+fn pawn_moves<'a>(
+    board: &'a [Piece; 64],
     frm: usize,
-    last: Option<&Move>,
+    last: Option<&'a Move>,
     bm_opp: u64,
     bm_board: u64,
     colour: bool,
-) -> Vec<Move> {
-    let mut l = bm2vec(match colour {
+) -> Box<dyn Iterator<Item = Move> + 'a> {
+    let iter = bm2vec(match colour {
         WHITE => {
             (BM_PAWN_CAPTURES[0][frm] & bm_opp)
                 | (BM_PAWN_STEP1[0][frm] & !bm_board)
@@ -163,8 +158,8 @@ fn pawn_moves(
                 | ((BM_PAWN_STEP1[1][frm] & !bm_board) >> 1) & (BM_PAWN_STEP2[1][frm] & !bm_board)
         }
     })
-    .iter()
-    .map(|&to| Move {
+    .into_iter()
+    .map(move |to| Move {
         frm,
         to,
         castle: false,
@@ -172,8 +167,7 @@ fn pawn_moves(
         kill: (board[to], to),
         val: pval(board[frm], to) - pval(board[frm], frm) - pval(board[to], to),
         hash: phashkey(board[frm], to) ^ phashkey(board[frm], frm) ^ phashkey(board[to], to),
-    })
-    .collect::<Vec<Move>>();
+    });
 
     // en passant
     if let Some(m) = last {
@@ -185,10 +179,10 @@ fn pawn_moves(
                 (1, m.frm + 1)
             };
 
-            l.extend(
+            return Box::new(iter.chain(
                 bm2vec(BM_PAWN_CAPTURES[cidx][frm] & 1 << idx)
-                    .iter()
-                    .map(|&to| Move {
+                    .into_iter()
+                    .map(move |to| Move {
                         frm,
                         to,
                         castle: false,
@@ -199,22 +193,22 @@ fn pawn_moves(
                             ^ phashkey(board[frm], frm)
                             ^ phashkey(board[to], to),
                     })
-                    .collect::<Vec<Move>>(),
-            );
+            ));
         }
     }
-    l
+
+    Box::new(iter)
 }
 
-fn king_moves(
-    board: &[Piece; 64],
+fn king_moves<'a>(
+    board: &'a [Piece; 64],
     frm: usize,
     bm_own_pieces: u64,
     bm_board: u64,
     end_game: bool,
-    can_castle: &[bool; 4],
+    can_castle: &'a [bool; 4],
     colour: bool,
-) -> Vec<Move> {
+) -> Box<dyn Iterator<Item = Move> + 'a> {
     // change king valuation in end_game
     let p = match (colour, end_game) {
         (WHITE, false) => K1,
@@ -242,9 +236,9 @@ fn king_moves(
          K2, R2, 55, 63, 39,),
     ];
 
-    bm2vec(BM_KING_MOVES[frm] & !bm_own_pieces)
-        .iter()
-        .map(|&to| Move {
+    Box::new(bm2vec(BM_KING_MOVES[frm] & !bm_own_pieces)
+        .into_iter()
+        .map(move |to| Move {
             frm,
             to,
             castle: false,
@@ -254,22 +248,21 @@ fn king_moves(
             hash: phashkey(board[frm], to) ^ phashkey(board[frm], frm) ^ phashkey(board[to], to),
         })
         .chain(
-            cc2.iter()
-                .filter(|(c, _, _, _, _, _)| *c)
-                .map(|(_, k, r, to, rfrm, rto)| Move {
+            cc2.into_iter()
+                .filter(|&(c, _, _, _, _, _)| c)
+                .map(move |(_, k, r, to, rfrm, rto)| Move {
                     frm,
-                    to: *to,
+                    to: to,
                     castle: true,
                     transform: (NIL, NIL),
-                    kill: (NIL, *to),
-                    val: pval(p, *to) - pval(p, frm) + pval(*r, *rto) - pval(*r, *rfrm),
-                    hash: phashkey(*k, *to)
-                        ^ phashkey(*k, frm)
-                        ^ phashkey(*r, *rto)
-                        ^ phashkey(*r, *rfrm),
+                    kill: (NIL, to),
+                    val: pval(p, to) - pval(p, frm) + pval(r, rto) - pval(r, rfrm),
+                    hash: phashkey(k, to)
+                        ^ phashkey(k, frm)
+                        ^ phashkey(r, rto)
+                        ^ phashkey(r, rfrm),
                 }),
-        )
-        .collect::<Vec<Move>>()
+        ))
 }
 
 fn transform(to: usize, colour: bool) -> (Piece, Piece) {
7 Likes
7

That was completely unnecessary. This sort of sarcasm doesn't help, and you didn't even remotely pinpoint the problem. The problem has nothing to do with interior mutability. OP's Rust code is just fine, he was having trouble with creating a correct signature for the lifetimes he actually needed. Parroting often-heard stuff based on a very superficial understanding of the problem (i.e., nothing more than reading the subtitle of the repo) is useless.

4 Likes
8

Nice work - yes, the closures have to own the data.

Works now - was interested to see if doing one .collect() at the end
rather than concatenating the itermediate sub vecs would be faster.
It isn't - about the same.

9

Where are you seeing the sarcasm? That's just observation. Python and Rust are built in radically different principles.

Python have dynamic dispatch built into, literally, every expression while Rust is built around monomorphisation. These two approaches are not the 100% full opposites, but very close to these:

  • Since in Python you are already paying for dynamic dispatch at every turn and there are no [easy] way to avoid it the best approach to make you code at least somewhat speed is to postpone actual work as much as possible.
  • Since Rust is built around monomorphisation the best way is to avoid dynamic dispatch as much as possible only using it in rare cases where savings achievable from it outweight it's nagatives. Often it's more efficient to do 10x more work than adding dynamic dispatch.

That means that if you write Python-in-Rust or you you write Rust-inPython then you are, by definition, creating subpar design on one language or another. Exceptions may exist is some simple cases, but not when you are doing some nontrivial algorithms.

OP's Rust design is not fine. It's Python-in-Rust design where you are trying to make everything as lazy as possible.

And if your goal is, explicitly, Python-in-Rust code then why adding extra complications to it? Just create mini-Python for your Rust code. This would be much simpler and easier for everyone involved.

10

No, that's just false. It's exactly the point. Rust encourages the use of iterators instead of upfront allocations too.

1 Like
11

Rust tolerates them because if LLVM base, not encourages them.

And they work decently well only when they can be monomorphised and your whole construct of few levels of indirections may be flattened and inlined.

So either your design is monomorphisible (and then it really doesn't make much sense to use dyn in it) or it becomes very slow (compared to “normal” Rust).

Yes, if you know both Rust and Python really well then you may write code which wouldn't performing too bad in either of them, but if you are not elite Python+Rust hacker then more likely than not your design would be atrocious from POV of both languages.

12

If that were true, then their use wouldn't be idiomatic; they probably wouldn't even exist in the language. Everything that's an Iterator today would be a method on Vec returning another Vec.

That's just not how it is.

This is false, too. Sometimes you need dynamic dispatch, and it's not "very slow". Here's the very thread from today that shows that the slowdown is in the single-digit percents.

Please, if you are not well-versed in the ecosystem of the language, and you can't prove your point with numbers, stop shaming people for using this or that language feature. What you have been doing repeatedly in the last couple of weeks has been very annoying and of no value.

11 Likes
13

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.