Class: CArray

Inherits:
Object
  • Object
show all
Defined in:
lib/carray/jit.rb,
lib/carray/jit/errors.rb,
lib/carray/jit/kernel.rb,
lib/carray/jit/c_function.rb

Defined Under Namespace

Modules: JIT

Compiling a block collapse

C functions collapse

Class Method Details

.jit_contract(*free_indices, &block) ⇒ CArray, CArray::JIT::CompiledKernel

CArray.jit_contract { |i, j, k| c[i,j] = a[i,k] * b[k,j] }

Every block parameter is an index. The ones that appear on the left are the cells written; the rest – k here – are summed over. An index that repeats is summed however often it repeats: q[i,i,i] is one index read at three positions, and the sum runs along the cube’s long diagonal.

No extent is given, because every index’s extent is fixed by the axes it addresses; an index whose axes disagree is an error, which is the shape check a contraction needs.

With no assignment the result is allocated and returned, with the free indices as its axes in the order the block named them:

c = CArray.jit_contract { |i, j, k| a[i,k] * b[k,j] }

Assigning into an array of your own says where to put it, and in what order its axes lie; it does not decide what is summed.

That a repeated index is summed is a statement about dimensions, which is the world the notation comes from: two dimensions met is an inner product, and there is no other reading. An index that numbers things – a point, a sample, a batch – is not a dimension, and x[p,k] * y[p,k] repeating p says “the same point”, not “sum over points”. Naming the result’s axes says which is meant:

CArray.jit_contract(:p) { |k| x[p,k] * y[p,k] } # one number per point CArray.jit_contract(:a) { square[a,a] } # the diagonal, not the trace CArray.jit_contract(:b, :i, :j) { |k| u[b,i,k] * v[b,k,j] } # a batch of products

The arguments are the result’s axes, in that order. What they say is which indices are free; what a repetition means is unchanged. So the rule is the convention’s, with a third clause: an index that repeats is summed, one that appears once is free, and a named one is free however often it appears – which is what puts the diagonal and the per-point quantity inside the notation instead of outside it. The list is all of the result’s axes rather than some of them – name one and you have named them all – so what is left out of it is summed, at however few positions it sits: jit_contract(:i) { |k| a[i,k] } is the row sums, which the convention alone cannot say. (sum(axis:) is the faster way to write that one, being a reduction rather than a contraction.) Naming is allowed even where the convention would have reached the same answer, which is how the result’s axes are put in another order.

Where the block assigns into an array of yours, the left-hand side has the result’s axes on it, and an axis there that the list left out is the list falling short rather than an index to sum – which is refused, and is the one place a short list is caught.

The sum is split into partial ones, as jit_for‘s reduction is: a contraction says which indices are summed and nothing about the order, so there is no order here to override. CArray::JIT.reassociate = false asks for the serial one, which is what a Ruby loop would take.

The block is read and compiled, never called, so it is not yielded to.

Parameters:

  • free_indices (Array<Symbol>) —

    the result’s axes, in order; empty to let the convention decide, which is an index appearing once.

Returns:

Raises:



285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
 
# File 'lib/carray/jit.rb', line 285

def self.jit_contract (*free_indices, &block)
  unless block
    raise JIT::Unsupported, "jit_contract needs a block"
  end
  unless free_indices.all? { |name| name.is_a?(Symbol) }
    raise JIT::Unsupported,
          "jit_contract's arguments are the result's axes, named as symbols, " \
          "as in `CArray.jit_contract(:p) { |k| x[p,k] * y[p,k] }`"
  end
  repeated = free_indices.tally.select { |_, count| count > 1 }.keys
  unless repeated.empty?
    raise JIT::Unsupported,
          "#{repeated.map { |name| "`#{name}`" }.join(', ')} names more than " \
          "one axis of the result; each axis is one index"
  end
  # Nothing named is the convention; naming none of them is a contraction
  # to a single number, and the two are different statements.
  JIT.run_contraction(block, free_indices.empty? ? nil : free_indices)
end

.jit_each(&block) ⇒ CArray::JIT::CompiledKernel

Returns the kernel compiled from block and run at every cell.

Element-wise means what it means in CArray: every cell is computed from the cells beside it in the other arrays, none reaches a neighbour, and the shapes are broadcast. So there is no index to name and no extent to give, and what changes is not the expression but how it runs – at the cell, in one pass, instead of one pass per operation with intermediate arrays in between.

CArray.jit_each { out = a + b * c }

The arrays are the variables the block closes over, and the expression is written the way CArray already writes it. Every name in the block is a cell – the loop is this compiler’s and is not written here – so the assignment is Ruby’s own: out = ... writes the cell of the array out names outside. A name that is not an array there is a local of the block’s, as it is anywhere else.

each is what CArray means by it: a cell. It is jit_for’s sibling and not its special case – a block that names an index is on a cell and can reach the cells around it, which is what makes a range and a direction matter, while an element-wise block has neither. And it is jit_map’s sibling in the other direction: the name says whether a value comes back.

Like jit_for, the name is this gem’s, and exists once carray/jit is required. Written without a compiler, the same computation is CArray.fuse’s – the expression itself, one pass per operation, with the intermediates this one does without.

Returns the compiled kernel, whose #c_source is the C that ran. The value of the computation is in the arrays the block wrote; ask for it back with jit_map instead.

The block is read and compiled, never called, so it is not yielded to.

Returns:

Raises:



125
126
127
128
129
130
131
132
133
134
135
 
# File 'lib/carray/jit.rb', line 125

def self.jit_each (&block)
  unless block
    raise JIT::Unsupported, "jit_each needs a block"
  end
  unless block.arity.zero?
    raise JIT::Unsupported,
          "this block names the arrays it reaches, so it takes no " \
          "parameters; for a loop that names its indices, see `jit_for`"
  end
  JIT.run_over_whole_arrays(block)
end

.jit_extern(prototype, from: nil, &block) ⇒ CArray::JIT::CFunction

Returns a callable for a C function someone else compiled, named by quoting its declaration, so that a kernel body – or Ruby – can call it:

j0 = CArray.jit_extern(“double j0(double)”, from: “libgsl”) CArray.jit_each { out = j0.call(x) }

Nothing is compiled here: extern is C’s word for a body that lives elsewhere, and finding it is Fiddle’s job. What this gem adds is that the kernel calls the address directly instead of reaching it per cell through Fiddle.

Parameters:

  • prototype (String) —

    the function’s C declaration, as C writes it.

  • from (String, nil) (defaults to: nil) —

    the library to open; nil searches the process.

Returns:



325
326
327
 
# File 'lib/carray/jit.rb', line 325

def self.jit_extern (prototype, from: nil, &block)
  JIT.extern(prototype, from: from, &block)
end

.jit_for(*extents, reassociate: nil, &block) ⇒ CArray::JIT::CompiledKernel

Returns the kernel compiled from block and run over extents.

The block’s parameters are the loop indices, and each extent is a Range or an Integer standing for 0...n, one per index:

CArray.jit_for(2…24) { |i| w = x * leg[i-1] wy = w - leg[i-2] leg[i] = wy + w - wy/i }

Naming an index is what lets a kernel reach a neighbouring cell, and reaching a neighbouring cell is what makes the range and the direction matter. A computation that reaches no neighbour names no index and needs no extent, and is written with CArray.jit_each or CArray.jit_map instead.

Arrays and scalars are the variables the block closes over, so nothing has to be named twice. Which way each axis runs is derived from the kernel’s own dependencies, not chosen: reading a cell the kernel will later write means that cell has to be reached in one particular order.

A block outside the compilable subset raises CArray::JIT::Unsupported rather than falling back to a Ruby loop. Nobody calls this method except to make a per-cell computation fast, so quietly doing the slow thing would answer a question that was not asked.

The name is this gem’s: CArray defines no jit_for of its own, so the method exists once carray/jit is required, and is documented where the subset is. An expression over whole arrays that needs no compiler is CArray.fuse’s.

reassociate: says whether a reduction’s accumulator may be split into partial sums. It defaults to CArray::JIT.reassociate, which is true: the answer is then not the one a serial Ruby loop reaches, and is usually the more accurate of the two, because splitting the accumulation is what limits the cancellation. Pass false for the serial order – for a compensated summation, whose algorithm is the order, or to check a kernel against the loop it replaces.

Returns the compiled kernel, whose CArray::JIT::CompiledKernel#c_source is the C that ran.

The block is read and compiled, never called, so it is not yielded to.

Parameters:

  • extents (Array<Range, Integer>) —

    one per loop index, an Integer standing for 0...n.

  • reassociate (Boolean, nil) (defaults to: nil) —

    whether a reduction’s accumulator may be split into partial sums; nil defers to CArray::JIT.reassociate.

Returns:

Raises:

  • (CArray::JIT::Unsupported) —

    when the block falls outside the recognized subset, or the extents do not match its parameters.



74
75
76
77
78
79
80
81
82
83
84
85
 
# File 'lib/carray/jit.rb', line 74

def self.jit_for (*extents, reassociate: nil, &block)
  unless block
    raise JIT::Unsupported, "jit_for needs a block"
  end
  if block.arity.zero?
    raise JIT::Unsupported,
          "jit_for's block names the cells it is on, so it takes the loop " \
          "indices as its parameters; a block that names none is " \
          "element-wise and belongs to jit_each"
  end
  JIT.run(extents, block, reassociate)
end

.jit_function(prototype, &block) ⇒ CArray::JIT::CFunction

Returns a callable for a C function of your own, written in Ruby and compiled here:

smoothstep = CArray.jit_function(“double ()(double)“) { |t| t t }

It is called from a kernel like any other, which gives kernels a body that can be factored and named, and its address may be handed to a C library that knows nothing about Ruby.

The block is read and compiled, never called, so it is not yielded to.

Parameters:

  • prototype (String) —

    the function’s C declaration, as C writes it.

Returns:

Raises:



344
345
346
 
# File 'lib/carray/jit.rb', line 344

def self.jit_function (prototype, &block)
  JIT.function(prototype, &block)
end

.jit_map(&block) ⇒ CArray

Returns a new array holding block‘s value at every cell.

The same block as jit_each, with its value asked for:

larger = CArray.jit_map { a > b ? a : b }

The last statement is the value every cell of the result gets, and the result is allocated here and returned, typed from that value. An assignment may be the last statement – in Ruby an assignment has the value it assigned – so a block may write an array of yours and hand the same value back.

The block is read and compiled, never called, so it is not yielded to.

Returns:

  • (CArray) —

    a new array, typed from the block’s value.

Raises:



154
155
156
157
158
159
160
161
162
163
164
 
# File 'lib/carray/jit.rb', line 154

def self.jit_map (&block)
  unless block
    raise JIT::Unsupported, "jit_map needs a block"
  end
  unless block.arity.zero?
    raise JIT::Unsupported,
          "this block names the arrays it reaches, so it takes no " \
          "parameters; for a loop that names its indices, see `jit_for`"
  end
  JIT.run_over_whole_arrays(block, map: true)
end

.jit_stencil(*arrays, border: :mask, type: nil, into: nil, &block) ⇒ CArray

Returns a new array holding block‘s value at every cell, computed from windows onto arrays.

A stencil: every cell from the ones around it, with the loop implied.

smoothed = CArray.jit_stencil(image) { |a| 0.25 * (a[-1, 0] + a[1, 0] + a[0, -1] + a[0, 1]) }

The arrays are given rather than closed over, and the block’s parameters are windows onto them, in that order: a[0, 0] is the cell, a[-1, 1] its neighbour. The block’s value is what the cell gets, as jit_map’s is, and the result comes back – an array of the same shape.

Naming a window rather than an index is what lets the edge be said at the
call rather than written into the loop. Where the window falls off the
array there is nothing to read, and border: says what to do about it:

mask the cell is UNDEF – it was not computed (the default)

skip the cell is left as it was found

The default is :mask because CArray can say “not computed”, and a border of zeros that means the same thing cannot be told from zeros that were computed.

type: names the array to collect into; without it the type is the block’s value’s, as jit_map’s result is. into: writes into an array of yours instead, and then the type is that array’s.

The block is read and compiled, never called, so it is not yielded to.

Parameters:

  • arrays (Array<CArray>) —

    the arrays the block has windows onto, in the order its parameters name them.

  • border (Symbol) (defaults to: :mask) —

    :mask to leave an uncomputed cell UNDEF, :skip to leave it as it was found.

  • type (Symbol, nil) (defaults to: nil) —

    the data type to collect into; nil takes the block’s value’s.

  • into (CArray, nil) (defaults to: nil) —

    an array of yours to write into, which then decides the type.

Returns:

  • (CArray) —

    into when it is given, otherwise a new array.

Raises:

  • (CArray::JIT::Unsupported) —

    when the block falls outside the recognized subset, when no array is given, or when both type and into are.



209
210
211
212
213
214
215
216
217
218
219
 
# File 'lib/carray/jit.rb', line 209

def self.jit_stencil (*arrays, border: :mask, type: nil, into: nil, &block)
  unless block
    raise JIT::Unsupported, "jit_stencil needs a block"
  end
  if arrays.empty?
    raise JIT::Unsupported,
          "jit_stencil takes the arrays its block has windows onto, as in " \
          "`CArray.jit_stencil(image) { |a| ... }`"
  end
  JIT.run_stencil(arrays, block, border, type, into)
end

Instance Method Details

#jit_init(reassociate: nil, &block) ⇒ CArray

Gives every cell of self the block’s value at its indices, and returns self.

The block takes one parameter per axis, as a constructor block does, and its value is what the cell at those indices gets:

CArray.int32(1000, 1000).jit_init { |i, j| (i + j) % 2 }

That is what CArray.int32(n, n) { |i, j| ... } says, without the Ruby call per cell: the constructor form is map_index!, which leaves C for every element and comes back, and this one compiles the body and runs the whole loop as C.

It is the only member of the family that is an instance method, because the array being written is the receiver. jit_for runs the same loop and has to be given both the index space and the array to write into – CArray.jit_for(n, n) { |i, j| z[i, j] = ... } – where here the extents are the receiver’s shape and the target is the receiver, so neither is said twice.

Reach for it when the values are a formula over the indices that will not go through whole-array arithmetic. Where it will, that needs no compiler and is faster still: a checkerboard is (i[nil, :_] + i[:_, nil]) % 2 over an index vector, and a sequence or a random fill has seq! and random! already. What is left for this method is the formula that cannot be said that way – a branch per cell, a value looked up, a recurrence along an axis.

A block outside the compilable subset raises CArray::JIT::Unsupported, as every other entry point here does. Nobody writes jit_init except to have the compiled loop, so quietly running the slow one would answer a question that was not asked – write the constructor block when the slow one is what is wanted.

The block is read and compiled, never called, so it is not yielded to.

Parameters:

Returns:

Raises:

  • (CArray::JIT::Unsupported) —

    when the block falls outside the recognized subset, or names a number of indices other than ndim.



389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
 
# File 'lib/carray/jit.rb', line 389

def jit_init (reassociate: nil, &block)
  unless block
    raise JIT::Unsupported, "jit_init needs a block"
  end
  if block.arity.zero?
    raise JIT::Unsupported,
          "jit_init's block takes the indices of the cell it computes, one " \
          "per axis, as a constructor block does; a block that names none " \
          "computes from other arrays and belongs to jit_each"
  end
  # A splat or an optional parameter makes the arity negative, and the
  # count in the message below a number nobody wrote.  The block reader
  # refuses both a few steps later; here there is an arity to compare, and
  # -1 is not one.
  if block.arity.negative?
    raise JIT::Unsupported,
          "jit_init's block names one index per axis, and names them as " \
          "required parameters; this one takes a splat or an optional " \
          "parameter, which says nothing about how many axes it is for"
  end
  unless block.arity == ndim
    raise JIT::Unsupported,
          "this array has #{ndim} #{ndim == 1 ? 'axis' : 'axes'} and the " \
          "block names #{block.arity} " \
          "#{block.arity == 1 ? 'index' : 'indices'}; jit_init fills every " \
          "cell, so there is one index per axis"
  end
  JIT.run(dim, block, reassociate, into: self)
end