Indexable::Mutable methods acting on part of the sequence?

Help & Support
1

I had to rotate the first n elements of an array and ended up doing this:

Slice.new(array.to_unsafe, n).rotate!(-1)

Is there a better way? How about adding start, count and/or start..end parameters to all Indexable::Mutable “*!” methods (like #fill has)?

2

I thing it is better to get slice from array than to litter all methods with arguments. Question about converting array to slice appear sometimes (Array#slice · Issue #5173 · crystal-lang/crystal · GitHub Why does Array not have a `to_slice` method? · Issue #9745 · crystal-lang/crystal · GitHub maybe there is more), but it is unsafe if you keep a reference to this slice and array is later resized.
Maybe better API would be

array.slice(0...n) do |slice|
  slice.rotate!(-1)
end

in a short form array.slice(0...n) &.rotate(-1)
This way API talk to us: that slice pointer is not for storing but for local operations.

1 Like
3

But that isn’t going to work on, for example, Deque, or any Indexable that isn’t implemented as a contiguous area of memory.

I don’t think adding a couple of named arguments can be considered “littering”, especially those. In Common Lisp, for instance, almost all sequence functions have :start and :end keyword arguments and they are very useful. It would be a little more complicated in Crystal because both start/count and range are used to express subsequences, but consistently having the signature of every Indexable[::Mutable] method that doesn’t modify the object’s size end in

..., *, start=0, count=nil, range=nil)

would be worthwhile, IMHO.

4

Slice idea still looks more elegant to me from both point of usage and point of implementation. Maybe slice for Indexable can return “virtual slice” that forward calls of unsafe_put and unsafe_fetch to parent object.

5

Here is a proof of concept how they could be implemented: Carcin

record VirtualSlice(T, X), parent : X, start : Int32, size : Int32 do
  include Indexable::Mutable(T)

  def unsafe_put(index : Int, value : T)
    @parent.unsafe_put(index + @start, value)
  end

  def unsafe_fetch(index : Int)
    @parent.unsafe_fetch(index + @start)
  end
end

module Indexable::Mutable(T)
  def slice(start : Int32, count : Int32, &)
    slice = VirtualSlice(T, typeof(self)).new(self, start, count)
    yield(slice)
  end
end

arr = Deque.new([1, 2, 3, 4, 5])
puts arr
arr.slice(0, 3, &.rotate!(-1))
puts arr
arr.slice(0, 3) { |x| x.slice(0, 2, &.rotate!(-1)) }
puts arr
2 Likes
6

That’s a good solution, too. It’s less foolproof tho, since the slices (even this virtual slice) can be invalidated inside the block. But we aren’t fools, are we? ;)

I wonder if the Crystal team would consider adding this (or the extra parameters) to the stdlib…

7

This approach is certainly an interesting solution.

A concern with this generalization is that it doesn’t directly profit from optimizations in the underlying container’s implementation.

To pick up on your example, Array#rotate! overrides Indexable::Mutable#rotate! using a more efficient algorithm that takes specifics of its data buffer into account.

I suppose we could move these optimizations to VirtualSlice. But that seems impractical, especially when considering integration of container types outside stdlib.

If we pass the intended range directly as parameter to the method, performance optimizations could be trivially used.

8

But this won’t be safe either, as you can still leak the slice out of the block

9

I wonder if it’s possible to have a safe slice, that would raise of the content is invalid. But then, it might just be better performance wise to split the array, work on the sub -part, and then rejoin.

10

A language feature to forbid the VirtualSlice in the block from being captured would be nice, i.e. RFC 4 as a semantic directive rather than an optimization opportunity. IIRC Swift has something like that

11

Yeah, but that still wouldn’t help the case in which the array is grown while inside the block

12

Multi-threading/concurrency safety is a completely separate issue though. It’s not specific to this use case. Any existing method on Array is exposed to that exactly like any additional ones we’re discussing here.

1 Like
13

I suppose we could move these optimizations to VirtualSlice.

I think that for Array (and other containers that can guarantee that memory is contigious ) #slice can yield Slice instead of VirtualSlice. Optimizations for Slice are already applied.

14

It’s not a matter of concurrency, it’s for perfectly sequential code. But it’s true that growing an array while iterating it also brings trouble.