Module: CArray::JIT

Defined in:
lib/carray/jit.rb,
lib/carray/jit/errors.rb,
lib/carray/jit/kernel.rb,
lib/carray/jit/c_function.rb

Overview

The compiler behind CArray.jit_*: it reads a block, generates C for it, builds it and calls it. What is public here is the reassociation default and the kernel cache; the rest is the machinery.

Defined Under Namespace

Classes: CFunction, CType, CompilationError, CompiledKernel, Error, Unsupported

Constant Summary collapse

FRAME_BORDERS =

What the frame gets. Two kinds: :mask and :skip are answers about the frame cells themselves -- mark them, or leave them -- and nothing is computed for a cell that was not computed. The other three say what a read outside the array gives, so the frame is computed after all, by a second walk with that rule written into its reads.

[:mask, :skip].freeze
EMPTY_ARRAYS =

Handed where there is nothing to take out of the line-up, so that the common case allocates nothing.

{}.freeze
PREFIX =

A C function a kernel body can call, and that C can be handed back.

The binding is borrowed from Fiddle -- Fiddle::Handle finds the library and the symbol, and Fiddle::CParser decides the ABI code of a type, which is the same path Fiddle::Importer#extern takes. The call is not borrowed: reaching a function through Fiddle::Function costs a few hundred nanoseconds per cell, against single digits from compiled C. Fiddle is asked where the function is; the kernel calls it.

The address travels to the kernel in a buffer, the way a captured scalar already does, rather than being linked against. That means no -l flag, no library path at compile time, and a compiled kernel that does not depend on which library the function came from -- so f.call(a) compiles once and serves every function of that signature. The namespace every symbol this compiler writes sits in, and that is not tidiness. A name the C already knows is the dangerous case, and the dangerous case is the one that does not fail: double sin(double) matches math.h's declaration, so the generated file defines libm's sin and the shared object exports it -- where symbols are interposable, that replaces sine for whatever loads it later. A mismatched signature is a compile error and would have been noticed; this one would not.

Here rather than beside function_symbol, which writes the names, because CFunction#c_source_as has to refuse one as well: a caller naming its own symbol may not name one in here.

"carray_jit_"

Class Attribute Summary collapse

Kernel cache collapse

Class Method Summary collapse

Class Attribute Details

.call_provider ⇒ Object

Asked at a jit_call site before anything is compiled, and answering nil means "not mine, compile it". What it is handed is the prototype, the block -- whose binding says which method and which module the site is in -- and the names the declaration gave. What it answers is anything that responds to call.

There is one client and it is carray-jit-aot, which builds these same sites into a shared object ahead of the program; a machine running that gem then reaches no compiler. Left here rather than patched in from there, because a gem reaching into another's method to change what it does is the arrangement that breaks quietly.



969
970
971
 
# File 'lib/carray/jit/c_function.rb', line 969

def call_provider
  @call_provider
end

.reassociate ⇒ Boolean

Returns whether a reduction's accumulator may be split when the call site does not say.

Returns:

  • (Boolean) —

    whether a reduction's accumulator may be split when the call site does not say.



446
447
448
449
 
# File 'lib/carray/jit.rb', line 446

def reassociate
  return @reassociate unless @reassociate.nil?
  @reassociate = ENV["CARRAY_JIT_REASSOCIATE"] != "0"
end

Class Method Details

.address_array_names(source, node, c_functions) ⇒ Object

Which names the block only hands to a C function whole. Cached for the reason the captured names are: jit_each is re-entered on every call, so anything read off the source here is read on every call, and walking the tree again cost the element-wise pass 1.7x before this was memoized.

The answer depends on the declarations as well as the source -- a parameter that takes a pointer is what makes an argument an address pass -- so the signatures are part of the key, as they are for the map probe. Nothing below the signature can change the answer: the scan asks indexable? and nothing else.



1647
1648
1649
1650
1651
1652
1653
1654
 
# File 'lib/carray/jit.rb', line 1647

def address_array_names (source, node, c_functions)
  key = [source, c_functions.transform_values(&:signature)]
  cached = address_name_cache[key]
  return cached if cached
  address_name_cache[key] =
    Analyzer.address_array_names(source, node: node,
                                 c_functions: c_functions)
end

.allocate_map_result(source, node, arrays, scalars, shape, c_functions, randoms = {}) ⇒ Object

The result has to be sized and typed before there is a kernel to ask, so the block is analyzed once without being compiled -- the same thing a returned contraction does, for the same reason.



1190
1191
1192
1193
1194
 
# File 'lib/carray/jit.rb', line 1190

def allocate_map_result (source, node, arrays, scalars, shape, c_functions,
                         randoms = {})
  type = probe_map(source, node, arrays, scalars, c_functions, randoms)
  CArray.send(type, *(shape.empty? ? [1] : shape))
end

.allocate_result(source, node, arrays, scalars, free_indices = nil, c_functions = {}) ⇒ Object

A contraction with nothing to assign into needs its result sized and typed before there is a kernel to ask, so the block is analyzed once without being compiled. Returns nil when the block assigns into an array of its own.



780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
 
# File 'lib/carray/jit.rb', line 780

def allocate_result (source, node, arrays, scalars, free_indices = nil,
                     c_functions = {})
  probe = probe_contraction(source, node, arrays, scalars, free_indices,
                            c_functions)
  return nil unless probe
  free, index_axes, type = probe
  shape = free.map do |index|
    extents = index_axes.fetch(index).map { |array, axis|
      [arrays.fetch(array).dim[axis], array, axis]
    }
    distinct = extents.map(&:first).uniq
    if distinct.size > 1
      described = extents.map { |extent, array, axis|
        "`#{array}` axis #{axis} is #{extent}"
      }.join(", ")
      raise Unsupported,
            "`#{index}` addresses axes of different extents: #{described}"
    end
    distinct.first
  end
  CArray.send(type, *(shape.empty? ? [1] : shape))
end

.block_cache ⇒ Object

Keyed by instruction sequence, which CRuby hands back as the same object for every Proc made from one block literal. That makes it a free identity for the block, and keeps the file from being read and parsed again on each call.

The key is held weakly. A block literal in a file keeps its sequence for the life of the process, but every eval makes a new one -- in a console, or in code that builds its kernels as text -- and a Hash kept each of them alive along with a parse of the whole script it came from, for as long as the process ran. Before Ruby 3.3 there is no WeakKeyMap and the cache is a Hash as it was.



1672
1673
1674
 
# File 'lib/carray/jit.rb', line 1672

def block_cache
  @block_cache ||= new_block_cache
end

.broadcast(arrays) ⇒ Object

CArray lines the shapes up; a stretched axis comes back as a stride of zero, which the kernel addresses like any other stride. CArray leaves a CScalar as it is, because its own kernels know to read one cell of it for every cell of everything else. This loop does not know that -- it addresses what it is handed -- so the CScalar is first referred to as the one-cell array it already is, and comes back from the broadcast as the stretched view a one-cell CArray comes back as. The referred view is the same memory, so a write still lands.

One axis per axis of what it is standing beside, rather than the one axis it would have had on its own: CArray.broadcast stretches a size-1 axis but does not invent an axis that is missing, so [1] against a [2, 3] is an ndim mismatch rather than a scalar. A CScalar has no shape of its own to contradict this -- being shapeless is what it is for -- so it takes the rank of the operands that do, and stretches on every axis, which is what CArray's own operators give for the same expression.



1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
 
# File 'lib/carray/jit.rb', line 1434

def broadcast (arrays)
  values = arrays.values
  rank = values.reject { |value| value.is_a?(CScalar) }
               .map(&:rank).max || 1
  values = values.map { |value|
    value.is_a?(CScalar) ? value.refer(value.data_type, [1] * rank) : value
  }
  aligned = values.size == 1 ? values : CArray.broadcast(*values)
  [arrays.keys.zip(aligned).to_h, aligned.first.dim]
end

.cache_byte_size ⇒ Integer

Returns the bytes this environment's cache holds.

Returns:

  • (Integer) —

    the bytes this environment's cache holds.



1744
1745
1746
 
# File 'lib/carray/jit.rb', line 1744

def cache_byte_size
  Compiler.byte_size
end

.cache_directory ⇒ String

Returns the directory this environment's kernels are kept in, named for the versions and architecture they were built for.

Returns:

  • (String) —

    the directory this environment's kernels are kept in, named for the versions and architecture they were built for.



1702
1703
1704
 
# File 'lib/carray/jit.rb', line 1702

def cache_directory
  Compiler.cache_directory
end

.cache_entry_count ⇒ Integer

Returns the number of kernels this environment has cached.

Returns:

  • (Integer) —

    the number of kernels this environment has cached.



1739
1740
1741
 
# File 'lib/carray/jit.rb', line 1739

def cache_entry_count
  Compiler.entry_count
end

.cache_root ⇒ String

Returns the directory holding one entry per environment.

Returns:

  • (String) —

    the directory holding one entry per environment.



1707
1708
1709
 
# File 'lib/carray/jit.rb', line 1707

def cache_root
  Compiler.cache_root
end

.cache_root=(path) ⇒ void

This method returns an undefined value.

Puts this application's kernels somewhere of its own, rather than in the cache shared under the home directory. Say it before the first kernel is compiled -- at the top of the program, beside the other requires:

CArray::JIT.cache_root = File.expand_path("../.jit-cache", __dir__)

Kernels already loaded keep working and what is already on disk stays where it is; this says where the next one is looked for and written. CARRAY_JIT_CACHE and CARRAY_JIT_NO_CACHE still come first, so whoever runs the program can put the cache somewhere writable or do without one. A directory inside a project wants to be ignored by the version control it sits in.

Parameters:

  • path (String, nil) —

    the directory, relative to where the program starts; nil restores the default.



1728
1729
1730
 
# File 'lib/carray/jit.rb', line 1728

def cache_root= (path)
  Compiler.cache_root = path
end

.call_here(prototype, block) ⇒ Object

A C function of your own, written in Ruby and compiled here:

square = CArray.jit_function("double (*)(double)") { |x| x * x + 1 }

double (*)(double) is the spelling C already has for the type of a function pointer, which is what this hands out. There is no name because nothing links by name -- the address is what travels -- so a name would have been invented to be looked at once. Writing one anyway is allowed, and becomes the symbol in the compiled object.

What comes back is the same object jit_extern hands out, so a kernel calls either without knowing which it has; compiled? is where the difference is still visible, along with the block, which it keeps. CArray.jit_call: compile the block, read the locals the declaration named, call.

Kept per call site rather than per body. A block literal is a fresh Proc every time the line runs, but its instruction sequence is the site's and does not change -- which is the key read_block already caches a block's source under.



908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
 
# File 'lib/carray/jit/c_function.rb', line 908

def call_here (prototype, block)
  site = RubyVM::InstructionSequence.of(block) if
    defined?(RubyVM::InstructionSequence)
  entry = site && call_sites[site]
  unless entry
    names = CDeclaration.parameter_names(prototype)
    if (missing = names.index(nil))
      raise Unsupported,
            "`#{prototype}` gives parameter #{missing + 1} no name, " \
            "and a name is what `jit_call` binds by -- it is the local " \
            "the call reads"
    end
    # A compiled function may already exist somewhere other than this
    # compiler's cache: built ahead of the program and shipped in a
    # shared object, which is what carray-jit-aot does with these same call
    # sites.  A provider is asked before anything is compiled and
    # answers nil for a site that is not its own -- the same position
    # `jit_extern` puts a function from a library in, said about a call
    # rather than about a name.
    compiled = call_provider &&
               call_provider.call(prototype, block, names)
    unless compiled
      # Nothing answered, so this one is compiled -- and the compiler
      # is loaded here rather than beside the method, so a program
      # whose sites were all answered never loads it.  `require` is
      # idempotent and this runs once per site.
      require "carray/jit"
      compiled = function(prototype, declared_parameters: names, &block)
    end
    entry = [compiled, names]
    call_sites[site] = entry if site
  end
  compiled, names = entry
  scope = block.binding
  compiled.call(*names.map { |local|
    begin
      scope.local_variable_get(local)
    rescue NameError
      raise Unsupported,
            "`#{prototype}` declares `#{local}`, and there is no local " \
            "by that name where the call stands. A declaration's " \
            "parameter names are what `jit_call` binds to"
    end
  })
end

.call_sites ⇒ Object 



954
955
956
 
# File 'lib/carray/jit/c_function.rb', line 954

def call_sites
  @call_sites ||= {}.compare_by_identity
end

.cell_names(arrays) ⇒ Object

An indexed kernel addresses what it is handed, so a CScalar among the captures is named here rather than stretched: it has no axis to walk, and the block says so by writing no index for it. The whole-array spellings have no such name to write, and broadcast instead.



1449
1450
1451
 
# File 'lib/carray/jit.rb', line 1449

def cell_names (arrays)
  arrays.select { |_, value| value.is_a?(CScalar) }.keys
end

.check_destination(into, free) ⇒ Object 



678
679
680
681
682
683
684
685
686
687
688
 
# File 'lib/carray/jit.rb', line 678

def check_destination (into, free)
  unless into.is_a?(CArray)
    raise Unsupported, "`into:` is an array to write into"
  end
  expected = free.empty? ? 1 : free.size
  unless into.rank == expected
    raise Unsupported,
          "`into:` has rank #{into.rank}, and the result's axes are " \
          "#{free.empty? ? 'none, which is one cell' : free.map { |name| "`#{name}`" }.join(', ')}"
  end
end

.check_free_indices(free, indices) ⇒ Object 



658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
 
# File 'lib/carray/jit.rb', line 658

def check_free_indices (free, indices)
  unless free.is_a?(Array) && free.all? { |name| index_name?(name) }
    raise Unsupported,
          "`free:` is the result's axes in order, named as symbols"
  end
  repeated = free.tally.select { |_, count| count > 1 }.keys
  unless repeated.empty?
    raise Unsupported,
          "#{repeated.map { |name| "`#{name}`" }.join(', ')} names more " \
          "than one axis of the result; each axis is one index"
  end
  missing = free - indices
  unless missing.empty?
    raise Unsupported,
          "#{missing.map { |name| "`#{name}`" }.join(', ')} " \
          "#{missing.size == 1 ? 'names no axis' : 'name no axis'} here"
  end
  free
end

.check_terms(terms) ⇒ Object

The names the synthesized source gives the terms. They are the source's own, so nothing outside chose them -- but an index may collide with one, and a collision would silently read an array as an index.



623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
 
# File 'lib/carray/jit.rb', line 623

def check_terms (terms)
  unless terms.is_a?(Array) && !terms.empty?
    raise Unsupported,
          "contract_terms takes the terms of a product, as in " \
          "`[[a, [:i, :k]], [b, [:k, :j]]]`"
  end
  terms.each do |term|
    unless term.is_a?(Array) && term.size == 2 && term.first.is_a?(CArray)
      raise Unsupported,
            "a term is an array and the indices it is read at, as in " \
            "`[a, [:i, :k]]`; got #{term.inspect}"
    end
    array, subscripts = term
    unless subscripts.is_a?(Array) && subscripts.all? { |name| index_name?(name) }
      raise Unsupported,
            "the indices of a term are symbols naming its axes, as in " \
            "`[a, [:i, :k]]`; got #{subscripts.inspect}"
    end
    unless subscripts.size == array.rank
      raise Unsupported,
            "a term names one index per axis: this array has rank " \
            "#{array.rank} and #{subscripts.size} " \
            "#{subscripts.size == 1 ? 'index' : 'indices'} were given"
    end
  end
  names = terms.each_index.map { |position| :"#{TERM_PREFIX}#{position}" }
  reserved = (names + [TARGET]) & terms.flat_map { |_, subscripts| subscripts }
  unless reserved.empty?
    raise Unsupported,
          "#{reserved.map { |name| "`#{name}`" }.join(', ')} names a term " \
          "here and cannot also be an index"
  end
  names
end

.clear_cache(everything: false) ⇒ Integer

Removes cached kernels.

Parameters:

  • everything (Boolean) (defaults to: false) —

    true to clear every environment, not only this one.

Returns:

  • (Integer) —

    the number of entries removed.



1753
1754
1755
 
# File 'lib/carray/jit.rb', line 1753

def clear_cache (everything: false)
  Compiler.clear(:everything => everything)
end

.clear_registry ⇒ void

This method returns an undefined value.

Forgets the kernels compiled in this process, so that the next call reaches the cache on disk rather than the one held in memory.



1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
 
# File 'lib/carray/jit.rb', line 1687

def clear_registry
  @registry = {}
  @capture_name_cache = {}
  @address_name_cache = {}
  @block_cache = new_block_cache
  @function_registry = {}
  # `jit_call`'s, keyed by the site rather than the body.
  @call_sites = {}.compare_by_identity
  @undef_cache = {}
  @probe_cache = {}
  @local_array_name_cache = {}
end

.compile(source, node: nil, origin: nil, array_names:, storage_types:, scalar_values:, c_functions: {}, masked: false, rank: nil, steps: nil, contract: false, result: nil, map: false, reassociate: false, cell_names: [], windows: [], border: nil, free_indices: nil, randoms: {}) ⇒ Object

Compiles for one set of array data types and one set of scalar types, and returns the same CompiledKernel for every later call with the same ones. Nothing on this path is cheap relative to running the kernel, so all of it is memoized.



1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
 
# File 'lib/carray/jit.rb', line 1528

def compile (source, node: nil, origin: nil, array_names:, storage_types:,
             scalar_values:, c_functions: {}, masked: false, rank: nil,
             steps: nil, contract: false, result: nil, map: false,
             reassociate: false, cell_names: [], windows: [], border: nil,
             free_indices: nil, randoms: {})
  # A kernel that mentions UNDEF is a masked one whatever its arrays
  # carry, and deciding that here means no caller has to remember it.
  masked ||= mentions_undef(source, node)
  key = [source, storage_types,
         scalar_values.transform_values { |value|
           TypeAssignment.scalar_type(value)
         },
         # The signature, not the address: `j0` and `y0` are the same
         # kernel, and it is compiled once.  One written here adds its
         # symbol, which stands for its body -- see `CFunction#kernel_key`.
         c_functions.transform_values(&:kernel_key),
         # Which generator each name is, and nothing about its state:
         # the C pasted for a draw is decided by the kind, and the seed
         # is data the kernel is handed at the call.  So two runs that
         # differ only in seed are one kernel, and the same kernel
         # serves a generator reset between calls.
         randoms.transform_values(&:generator),
         masked, rank, steps, contract, result, map,
         # A contraction whose free indices were named is not the kernel
         # the same source is without them, nor with them in another
         # order: the naming decides what is summed and what comes out.
         free_indices,
         # Which names are read at their one cell rather than walked:
         # the same source over a CScalar is a different kernel from
         # the same source over a one-cell CArray.
         cell_names,
         # Which names are windows: the same source read as a stencil is
         # not the same kernel as the same source read as a block that
         # named its indices.
         windows,
         # And what a window that falls off the array reads: the rule is
         # emitted into the frame's body, so two rules are two kernels.
         border,
         # The licence is part of the kernel, not of the call: it
         # decides what C is emitted, so the two spellings are two
         # kernels and the cache keeps them apart.
         reassociate]
  found = registry[key]
  return found if found
  registry[key] = build(source, node, array_names, storage_types,
                        scalar_values, c_functions, masked, rank, steps,
                        contract, result, origin, map, reassociate,
                        cell_names, windows, border, free_indices,
                        randoms)
end

.contract(source, arrays, free_indices, node: nil, origin: nil, scalars: {}, c_functions: {}) ⇒ Object

What a contraction is once its block has been read: a source, the arrays that source names, and which indices are free. Everything before this is about recovering those from a block; everything after is the same whatever recovered them, which is what lets contract_terms reach it with a source it wrote itself.



708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
 
# File 'lib/carray/jit.rb', line 708

def contract (source, arrays, free_indices,
              node: nil, origin: nil, scalars: {}, c_functions: {})
  result = allocate_result(source, node, arrays, scalars, free_indices,
                           c_functions)
  arrays = arrays.merge(RESULT => result) if result

  kernel = compile(source,
                   node: node,
                   origin: origin,
                   array_names: arrays.keys,
                   storage_types: arrays.transform_values(&:data_type_name),
                   scalar_values: scalars,
                   c_functions: c_functions,
                   masked: arrays.each_value.any? { |array| array.has_mask? },
                   contract: true,
                   result: RESULT,
                   # A contraction sums an index; which order it sums it
                   # in is not something the caller wrote, so splitting
                   # the sum into partial ones does not change what the
                   # contraction means.  Same licence `jit_for` takes.
                   reassociate: JIT.reassociate,
                   free_indices: free_indices,
                   cell_names: cell_names(arrays))

  refuse_aliased_result(kernel, arrays)
  extents = contraction_extents(kernel, arrays)
  if kernel.masked
    kernel.written_arrays.each do |name|
      array = arrays.fetch(name)
      array.mask = 0 unless array.has_mask?
    end
  end
  kernel.call(arrays, scalars, extents, c_functions)
  result || kernel
end

.contract_terms(terms, free:, into: nil) ⇒ CArray

Runs the contraction the terms describe, where a term is an array and the indices it is read at:

CArray::JIT.contract_terms([[a, [:i, :k]], [b, [:k, :j]]],
                         free: [:i, :j])            # a matrix product

It is jit_contract with the block already taken apart -- the same rules, the same errors, the same kernels -- for a caller that has the structure rather than a block to read. A contraction that was decided rather than written has no source, which is what this is for.

free: is the result's axes in order, and is required: a structure has no parameter list, so there is nowhere else for the order to be said. Every index that is not named is summed, and must appear at more than one position, exactly as in a block whose axes are named.

The terms are a product of element reads and nothing else. A summand that is more than that -- Math.exp(a[i,k]) * b[k,j], a division, a captured scalar, an index with an offset -- is written as a block and compiled by jit_contract; there is no structure here that says it.

Parameters:

  • terms (Array<Array>) —

    [array, [index, ...]] pairs.

  • free (Array<Symbol>) —

    the result's axes, in order.

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

    an array of yours to write into, which then decides the axis order and is what comes back.

Returns:

  • (CArray) —

    into when it is given, otherwise a new array.

Raises:

  • (CArray::JIT::Unsupported) —

    when the terms are malformed, or the contraction they describe is one the compiler refuses.



591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
 
# File 'lib/carray/jit.rb', line 591

def contract_terms (terms, free:, into: nil)
  names = check_terms(terms)
  indices = terms.flat_map { |_, subscripts| subscripts }
  free = check_free_indices(free, indices)
  arrays = names.zip(terms.map(&:first)).to_h

  factors = terms.each_with_index.map { |(_, subscripts), position|
    "#{names[position]}[#{subscripts.join(',')}]"
  }
  body = factors.join(" * ")
  if into
    check_destination(into, free)
    arrays[TARGET] = into
    # With every index summed the result is one number, which lives in a
    # one-cell array at a fixed subscript -- as it is written in a block.
    body = "#{TARGET}[#{free.empty? ? '0' : free.join(',')}] = #{body}"
  end
  summed = indices.uniq - free
  parameters = summed.empty? ? "" : "|#{summed.join(', ')}| "

  # The source the block would have had.  It is what the kernel cache is
  # keyed by, so the same terms under the same shapes reach the same
  # kernel however they were arrived at -- and the string is canonical,
  # which is the same service einsum's subscripts perform.
  result = contract("proc { #{parameters}#{body} }", arrays, free)
  into || result
end

.contraction_extents(kernel, arrays) ⇒ Object

Each index's extent comes from the axes it addresses. Where it addresses more than one and they differ, the contraction has no shape and says which axes disagreed.



864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
 
# File 'lib/carray/jit.rb', line 864

def contraction_extents (kernel, arrays)
  order = kernel.index_names + kernel.contracted_names
  order.map do |index|
    places = kernel.index_axes[index]
    extents = places.map { |array, axis| [arrays.fetch(array).dim[axis], array, axis] }
    distinct = extents.map(&:first).uniq
    if distinct.size > 1
      described = extents.map { |extent, array, axis|
        "`#{array}` axis #{axis} is #{extent}"
      }.join(", ")
      raise Unsupported,
            "`#{index}` addresses axes of different extents: #{described}"
    end
    [0, distinct.first, 1]
  end
end

.contraction_of(block, *free_indices) ⇒ Hash?

Reads a block as a contraction and returns the terms it is a product of, or nil when it is not one:

CArray::JIT.contraction_of(proc { |i, j, k| a[i,k] * b[k,j] })
#=> { :terms => [[a, [:i, :k]], [b, [:k, :j]]],
#     :free => [:i, :j], :summed => [:k], :scale => 1 }

A number multiplied into the product is not a term -- it has no indices and no cell -- so it comes back as :scale, which is 1 where there is none. a[i,k] * b[k,j] * 2.0 is the same contraction scaled, and a caller that rearranges it has to put the scale back: multiplying a sum by a number and multiplying each of its terms are the same arithmetic, but not the same rounding, and they are not the same computation type either where the number is wider than the cells.

This is the half of jit_contract that decides what is being computed, without compiling anything, for a caller that wants to rearrange it -- to contract two terms at a time, say, in an order it chose -- and then reach contract_terms with the pieces.

Nil means "there is nothing here to rearrange", not that the block is wrong: a summand that is more than a product of element reads (Math.exp(a[i,k]) * b[k,j], a division, a captured scalar, an index with an offset), or one that assigns into an array of its own. Such a block is still a contraction and jit_contract still compiles it; it is just not a product to be taken apart. A block that is not a contraction at all raises here, as it would there.

Parameters:

  • block (Proc) —

    the block, read and not called.

  • free_indices (Array<Symbol>) —

    the result's axes, as jit_contract takes them.

Returns:

  • (Hash, nil) —

    { terms:, free:, summed: }, or nil.

Raises:



503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
 
# File 'lib/carray/jit.rb', line 503

def contraction_of (block, *free_indices)
  node, source, = read_block(block)
  # As `jit_contract` reads them: naming none is the convention, which
  # is not the same as naming an empty list of axes.
  free_indices = nil if free_indices.empty?
  names = capture_names(source, node) - (free_indices || [])
  arrays, scalars, c_functions, randoms =
    split_captures(names, binding_of(block))
  refuse_a_generator(randoms, "a contraction", "the block is a summand " \
    "and runs once per term, so a draw in it would be one per term " \
    "rather than one per cell of the result")
  # A compiled function in the summand is not something the structure
  # carries; a captured number is, as the scale.
  return nil unless c_functions.empty?

  analyzer = Analyzer.new(source, node: node, array_names: arrays.keys,
                          contract: :probe, free_indices: free_indices,
                          cell_names: cell_names(arrays))
  statements = analyzer.body.statements
  # Locals before the summand are computation the structure cannot
  # carry either; an ElementWrite last is the assigned form.
  return nil unless statements.size == 1
  factors = product_terms(statements.last, arrays, scalars)
  return nil unless factors
  terms, scale = factors
  return nil if terms.empty?

  free = analyzer.probe_free_names
  { :terms => terms, :free => free,
    :summed => terms.flat_map(&:last).uniq - free, :scale => scale }
end

.drive(kernel, aligned, scalars, c_functions, shape, sweeping) ⇒ Object

Which loop runs it. Both compute the same thing from the same compiled body -- what differs is who acquires the operands.

CArray's chunked sweep re-gathers an operand it cannot walk in place 32KB at a time, where the tiers here move the whole box the kernel touches, and for an element-wise pass that box is the whole array. Measured over two million doubles with a gather view as an operand: 1.3 ms either way, and 32KB of scratch against sixteen megabytes. With an entity operand the two are indistinguishable, so there is nothing to weigh. With a strided view there is: the tiers address it in place and the sweep re-gathers it, which is why #sweepable_pass? asks what tier each operand would be opened at and not only what shape it has.

It cannot always. A body that asks about a mask has no per-cell mask in a chunk to ask it of; operands that disagree on their element count are broadcast here and refused there; and a kernel of rank two or more addresses its operands by axis, which one flat run of cells cannot supply.



960
961
962
963
964
965
966
967
 
# File 'lib/carray/jit.rb', line 960

def drive (kernel, aligned, scalars, c_functions, shape, sweeping)
  if sweeping
    kernel.sweep(aligned, scalars, c_functions)
  else
    kernel.call(aligned, scalars, shape.map { |extent| [0, extent, 1] },
                c_functions)
  end
end

.extern(prototype, from: nil, &block) ⇒ Object

A C function someone else compiled, reached by quoting its declaration:

j0 = CArray.jit_extern("double j0(double)", from: "libgsl")

from is where to look -- a path or library name, a Fiddle::Handle, or nothing at all, which searches what the process has already loaded.

extern is C's own word for a body that lives elsewhere, and that is all this does: it asks Fiddle where the function is. Nothing is compiled here, which is the difference from jit_function and the reason the two are not one method with a branch in it.

The declaration is C rather than a vocabulary of this compiler's own, because what is declared is a C function and the types it has to meet belong to whatever will call it. void *params is the point of the exercise, not an edge of it.



872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
 
# File 'lib/carray/jit/c_function.rb', line 872

def extern (prototype, from: nil, &block)
  if block
    raise Unsupported,
          "`jit_extern` finds a function already compiled, so a body " \
          "here would be dropped; compile one with `CArray.jit_function`"
  end
  name, return_type, parameters = CDeclaration.parse(prototype)
  unless name
    raise Unsupported,
          "`#{prototype}` names no function to find; give the name, as " \
          "in `double j0(double)` -- or write the body and compile it " \
          "with `CArray.jit_function`"
  end
  bind_c_function(prototype, name, return_type, parameters, from)
end

.frame_boxes(bounds, shape) ⇒ Object

The frame, cut into boxes the loop can walk. Peeling one axis at a time and taking the interior of the axes already peeled is what keeps them from overlapping: a cell in two of them would be computed twice, and a stencil that wrote a cell twice would be a different thing depending on which write landed last.

Two boxes per axis, so 2 * rank of them however wide the window is -- the corners come with the axis peeled first rather than being cases of their own.



1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
 
# File 'lib/carray/jit.rb', line 1116

def frame_boxes (bounds, shape)
  boxes = []
  shape.each_index do |axis|
    from, to, = bounds[axis]
    [[0, from], [to, shape[axis]]].each do |low, high|
      next if low >= high
      box = shape.each_index.map { |other|
        if other == axis then [low, high, 1]
        elsif other < axis then bounds[other]
        else [0, shape[other], 1]
        end
      }
      boxes << box
    end
  end
  boxes
end

.free_and_assigned_names(source, node = nil) ⇒ Object

Which names the block reaches for, and which it assigns. Both are properties of the source, so both are cached; what each name is is a property of the binding, and is settled outside the cache.



1602
1603
1604
1605
1606
1607
 
# File 'lib/carray/jit.rb', line 1602

def free_and_assigned_names (source, node = nil)
  cached = capture_name_cache[source]
  return cached if cached
  capture_name_cache[source] =
    Analyzer.free_and_assigned_names(source, node: node)
end

.function(prototype, declared_parameters: nil, &block) ⇒ Object 



971
972
973
974
975
976
977
978
979
980
981
 
# File 'lib/carray/jit/c_function.rb', line 971

def function (prototype, declared_parameters: nil, &block)
  unless block
    raise Unsupported,
          "a function is compiled from a block, and none was given -- " \
          "or find one already compiled with " \
          "`CArray.jit_extern(#{prototype.inspect})`"
  end
  name, return_type, parameters = CDeclaration.parse(prototype)
  compile_c_function(prototype, name, return_type, parameters, block,
                     declared_parameters)
end

.index_name?(name) ⇒ Boolean

An index is interpolated into the source this writes, so it has to be a name Ruby reads back as a local variable. :end and :do would not parse at all, and :nil and :self would come back as something else -- all of them as an error about a source the caller never wrote.

Returns:

  • (Boolean) 


694
695
696
697
698
699
700
701
 
# File 'lib/carray/jit.rb', line 694

def index_name? (name)
  return false unless name.is_a?(Symbol)
  text = name.to_s
  return false unless text.match?(/\A[a-z_][A-Za-z0-9_]*\z/)
  parsed = Prism.parse("#{text} = 1")
  parsed.errors.empty? &&
    parsed.value.statements.body.first.is_a?(Prism::LocalVariableWriteNode)
end

.local_array_names(source, node = nil) ⇒ Object

Which names the block makes arrays of its own under. A property of the source, so it is cached with the rest of them -- and for the reason the captured names are: an element-wise pass re-enters on every call, so a walk of the tree here is a walk per call. It was the last of this family still being walked, at 3.3 us of a call.



1614
1615
1616
1617
1618
1619
 
# File 'lib/carray/jit.rb', line 1614

def local_array_names (source, node = nil)
  cached = local_array_name_cache[source]
  return cached if cached
  local_array_name_cache[source] =
    Analyzer.local_array_names(source, node: node)
end

.mark_frame(result, bounds, shape) ⇒ Object

A frame cell is one the loop does not write, so :mask marks it before the loop rather than during it: what says "not computed" is a mask byte, and the cells are named by the same bounds the loop is given. This is the whole of :mask -- there is nothing to compute for a cell that was not computed.



1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
 
# File 'lib/carray/jit.rb', line 1139

def mark_frame (result, bounds, shape)
  shape.each_with_index do |extent, axis|
    from, to, = bounds[axis]
    [(0...from), (to...extent)].each do |span|
      next if span.size.zero?
      index = Array.new(shape.size) { nil }
      index[axis] = span
      result[*index] = UNDEF
    end
  end
end

.mentions_undef(source, node = nil) ⇒ Object

A kernel that mentions UNDEF is a masked kernel whatever its arrays happen to carry: it asks about masks, or makes them. Checked here because the answer is needed before the kernel is built.



1582
1583
1584
1585
1586
 
# File 'lib/carray/jit.rb', line 1582

def mentions_undef (source, node = nil)
  cached = undef_cache[source]
  return cached unless cached.nil?
  undef_cache[source] = Analyzer.mentions_undef?(source, node: node)
end

.product_terms(node, arrays, scalars) ⇒ Object

The product's terms and what multiplies them, or nil where the tree is anything but a product of cells and numbers.



537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
 
# File 'lib/carray/jit.rb', line 537

def product_terms (node, arrays, scalars)
  case node
  when BinaryOperation
    return nil unless node.operator == :*
    left = product_terms(node.left, arrays, scalars)
    right = left && product_terms(node.right, arrays, scalars)
    right && [left.first + right.first, left.last * right.last]
  when ElementRead
    subscripts = node.subscripts
    return nil unless subscripts.all? { |index, offset|
      index && offset.is_a?(Integer) && offset.zero?
    }
    [[[arrays.fetch(node.array), subscripts.map(&:first)]], 1]
  when IntegerLiteral, FloatLiteral
    [[], node.value]
  when CaptureRead
    value = scalars[node.name]
    value.is_a?(Numeric) ? [[], value] : nil
  end
end

.read_once_where_the_pass_writes(aligned, written_names) ⇒ Object

a = b * 2.0 reads the whole of the right-hand side and then assigns, which is what the expression means in Ruby and what CArray's own operators do. A kernel walks cell by cell instead, and that is the same thing only while no cell it reads is a cell it has written: two overlapping views of one array -- hi = lo * 2.0 for blocks that share six cells, a transpose written over itself -- read the output back as input, cell by cell. A gather is copied before the loop and keeps the meaning; a strided view is addressed in place, which is what makes it fast and what leaves it exposed here.

So an operand that is read, and shares a root with one that is written without being that array itself, is copied once before the loop. a = a + 1.0 is not that case -- the cell read is the cell written, as in Ruby -- and neither is a pass whose arrays are separate, which is nearly all of them.



1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
 
# File 'lib/carray/jit.rb', line 1366

def read_once_where_the_pass_writes (aligned, written_names)
  written = written_names.filter_map { |name| aligned[name] }
  return aligned if written.empty?
  roots = written.map { |array| root_of(array) }
  aligned.to_h do |name, array|
    next [name, array] if written_names.include?(name)
    next [name, array] if written.any? { |other| other.equal?(array) }
    shared = roots.any? { |root| root.equal?(root_of(array)) }
    [name, shared ? array.copy : array]
  end
end

.refuse_a_transferred_alias(kernel, arrays) ⇒ Object

An operand a kernel cannot walk -- a gather, a lazy array -- is copied into a buffer before the loop and copied back after it. For an expression over whole arrays that is what the expression means: the right-hand side is read, then assigned. An indexed kernel means the loop instead, and a loop reads a cell when it reaches it: where the array copied is one the loop also writes, the copy is a photograph of cells that go on changing. y[i] = gy[i] + 1.0, with gy a gather of y, gave the reversal of the array it started with where the Ruby loop sees its own writes; and a gather written beside a direct write put the whole buffer back at the end, dropping the direct one.

Neither is a thing to fix by copying harder, so it is refused, with the loop that does mean something named: index the array itself and let the subscript do the gathering.



1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
 
# File 'lib/carray/jit.rb', line 1392

def refuse_a_transferred_alias (kernel, arrays)
  written = kernel.written_arrays.filter_map { |name| arrays[name] }
  return if written.empty?
  roots = written.map { |array| root_of(array) }
  arrays.each do |name, array|
    next unless Access.classify(array)[:tier] == Access::TIER_XFER
    root = root_of(array)
    # Another operand on the same storage, and one of the two written:
    # a copy taken before the loop cannot answer for either of them.
    # The array alone on its root is not that case -- what it scatters
    # back at the end, nothing in the loop was reading.
    others = arrays.each_value.reject { |other| other.equal?(array) }
                   .select { |other| root.equal?(root_of(other)) }
    next if others.empty?
    next unless written.any? { |one| one.equal?(array) } ||
                others.any? { |other| written.any? { |one| one.equal?(other) } }
    raise Unsupported,
          "`#{name}` cannot be walked as it stands, so the kernel would " \
          "work on a copy of it taken before the loop -- and the loop " \
          "writes the array it is a view of, which the copy would not " \
          "see. Index that array directly and let the subscript gather: " \
          "`a[order[i]]` rather than a view of `a`"
  end
end

.refuse_aliased_result(kernel, arrays) ⇒ Object

An array a contraction writes and also reads is a recurrence, which the analyzer refuses -- but it compares the names a block gave them, and two names may be one array. x = a is one, and so is a view of something being read: cells reached before the write see the old value and cells reached after see the new one, so the answer depends on the order and is not the contraction that was asked for.

This is where the arrays themselves are known, so it is where the question can be asked of them rather than of their names. Views are followed to what they are views of, since that is the memory two names would share.



755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
 
# File 'lib/carray/jit.rb', line 755

def refuse_aliased_result (kernel, arrays)
  kernel.written_arrays.each do |written|
    target = root_of(arrays.fetch(written))
    arrays.each do |name, array|
      next if name == written
      next unless root_of(array).equal?(target)
      same = arrays.fetch(written).equal?(array)
      raise Unsupported,
            "`#{written}` and `#{name}` are #{same ? 'the same array' : 'views of one array'}, " \
            "which this both writes and reads; that is a recurrence " \
            "rather than a contraction, and is written with jit_for. " \
            "Two views are refused by the storage they share rather " \
            "than by the cells, so two that share none are refused too"
    end
  end
end

.root_of(array) ⇒ Object 



772
773
774
 
# File 'lib/carray/jit.rb', line 772

def root_of (array)
  array.respond_to?(:root_array) ? array.root_array : array
end

.stale_cache_environments ⇒ Array<String>

Returns the environment directories no longer in use -- another version, or another architecture.

Returns:

  • (Array<String>) —

    the environment directories no longer in use -- another version, or another architecture.



1734
1735
1736
 
# File 'lib/carray/jit.rb', line 1734

def stale_cache_environments
  Compiler.stale_environments
end

.stencil_result(source, node, arrays, scalars, c_functions, windows, shape, type, into) ⇒ Object

Typed from the block's value, as jit_map's result is, unless the caller said otherwise. into: is checked against the shape here rather than by the kernel, so that a wrong array is refused before anything is compiled for it.



1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
 
# File 'lib/carray/jit.rb', line 1155

def stencil_result (source, node, arrays, scalars, c_functions, windows,
                    shape, type, into)
  if into
    unless into.is_a?(CArray) && into.dim == shape
      raise Unsupported,
            "`into:` takes an array of the stencil's own shape " \
            "#{shape.inspect}"
    end
    return into
  end
  chosen = type || probe_stencil(source, node, arrays, scalars,
                                 c_functions, windows, shape)
  CArray.send(chosen, *shape)
end

.sweepable_pass?(arrays, shape, masked) ⇒ Boolean

Whether CArray's sweep can run this pass, decided before there is a kernel -- because the answer changes what is compiled.

A chunk is one flat run of cells, and CArray already treats an operand as one: its acquire reads elements and the element size and never looks at the shape. So the arrays do not have to be flattened, and are not; what has to be flat is the kernel, which is compiled at rank one over the same cells rather than as a nest over the axes.

The one thing that cannot be flattened is a stretched operand. Broadcasting arrives as a stride of zero on an axis, and an axis is what a flat run has none of -- so cell k of the output would stop lining up with cell k of the stretched operand. Hence the test is that every operand already has the shape the pass covers, which is stricter than agreeing on the count of cells.

Returns:

  • (Boolean) 


907
908
909
910
911
912
913
914
915
 
# File 'lib/carray/jit.rb', line 907

def sweepable_pass? (arrays, shape, masked)
  return false unless Sweep.available?
  return false if masked
  return false if arrays.empty? || arrays.size > Sweep::MAX_ARITY
  return false unless arrays.each_value.all? { |array|
    array.rank.zero? || array.dim == shape
  }
  walkable_in_place?(arrays.each_value)
end

.walkable_in_place?(arrays) ⇒ Boolean

Whether the operands settle the question the shape leaves open.

The sweep re-gathers what it cannot walk in place, 32KB at a time, and that is a bargain against materialising the same operand whole -- but only where the tiers here would have to materialise it. So the tier each operand would be opened at is the rest of the decision:

TIER_XFER    neither can walk it, and the sweep holds 32KB where
           the tiers hold the whole box: the sweep runs
TIER_STRIDE  a column, a transpose, every other cell -- the tiers
           address it in place, and the sweep re-gathers it for
           nothing: the driver stays here
TIER_ENTITY  both walk the buffer, and the two are
           indistinguishable: the sweep runs, as it always did

Measured over two million doubles with a strided view as the operand: 0.9 ns/cell with the driver here against 6.1 ns/cell swept, and no scratch either way -- there was nothing the re-gather was buying.

Returns:

  • (Boolean) 


935
936
937
938
939
 
# File 'lib/carray/jit.rb', line 935

def walkable_in_place? (arrays)
  tiers = arrays.map { |array| Access.classify(array)[:tier] }
  return true if tiers.include?(Access::TIER_XFER)
  tiers.none? { |tier| tier == Access::TIER_STRIDE }
end