Mill Computing, Inc. Forums The Mill Architecture array bound checking

  • Author
    Posts
  • goldbug
    Participant
    Post count: 53
    #3063 |

    Is there anything mill specific to do array bounds check?

    for example:

    
    void foo()
    {
       int myarray1[3];
       int myarray2[3];
       int myarray3[3];
    
       // undefined behavior,  will probably override something in either array 1 or array 3
       // depending on how things are organized in the stack
       myarray2[3] = 5;
    }

    In other platforms we have valgrind, which adds array bounds checking instructions at great performance cost.
    Ideally the application would abort rather than continue silently, and doing the check would take no extra cycles.

    I suppose in this example the compiler could add range checking operations (lss, geq, pick and brtr), which would be “free” since they could be squeezed in the regular program instructions. But if the array size is not known as compile time such as when you receive a pointer to the array, it would be a lot more complicated.

  • Ivan Godard
    Keymaster
    Post count: 689

    Yes and no.
    We have to support C, and C has no arrays in expressions – any array name is promoted to a pointer. For explicit indexing where the type is known the compiler can insert explicit bounds checks, but often the underlying type is no longer known. For other languages, or under compiler option, checking using ordinary operations and the machine width does about as well as custom operations for bounds checking. The predicated fault op (for stores) and the one-legged NaR pick (for loads and LEA) are useful.

    Valgrind and similar tools check for access outside of an allocated object, not just array indexing. To do that properly requires capabilities or fat pointers, which break data structures that assume skinny pointers. We have some NYF support for this usage.

  • Validark
    Participant
    Post count: 21

    Does the Mill have any instructions that can directly support fat pointers? E.g. in Zig I can do cur = cur[1..];, where cur has a ptr and len field, each a machine word, and this will add 1 to the ptr and subtract 1 from len. It would be cool if addp e.g. could work directly on fat pointers. I.e. In the case that addp is given a fat pointer as an argument, it would simultaneously add to the pointer and subtract from the length, giving back a 16 byte fat pointer with the pointer half increased and the length half decreased (assuming you are on a Mill member with where each slot on the belt can hold 16 bytes). If the length goes below 0 it should return a NaR.

    • Ivan Godard
      Keymaster
      Post count: 689

      There is no direct ISA support for {addr, len} style descriptors. Instead descriptor arithmetic would use the machine width to update both fields independently. The performance would be the same, but does not require 128-bit data paths into the ALU and on the belt. There are many specialized kinds of smart/fat pointers in use, hidden behind the abstractions of the languages. It’s easy to invent one that satisfies a particular set of usage; it’s hard to make it general. For example, how does one get a {addr, len} pointer to iterate backwards? How are they garbage-collected? The ISA is not the place for these questions; the languages are.

      There is a mechanism to check the validity of a pointer per the C/C++ rules: points within the object or one element beyond. Violations get you a NaR. However, this is a validity check, not a range check. NYF.

  • Validark
    Participant
    Post count: 21

    Don’t higher-end Mills already support native 128 bit operations? Of course, machine width can support this feature as well but supporting {addr,len} pointers directly would allow one to run more operations simultaneously (on higher-end Mills), which could be a big win in some scenarios where you want to do two {addr+1,len-1} ops in a cycle while also doing something else. It would also make things fall off the belt slower when using multiple fat pointers. The {addr,len} scheme doesn’t seem terribly specialized to me. To me it seems quite general-purpose and applicable to a wide variety of programming languages. I think most languages probably use {addr,len} all over the place. In many cases things have a capacity field too but that doesn’t change during iteration so that can sit elsewhere.

    With regards to backwards iteration, I’d assume one could use subp, although I don’t particularly care what the semantics are as much. I have personally only used fat pointers for forward iteration and I do not know how most languages support backwards iteration, if they even do (in Go, C#, and JavaScript, for example, one cannot go backwards with a blessed for..of/foreach loop, you have to manually index in or reverse the data in an array). The languages that do support backwards iteration appear not to give access to any data besides the current element (and perhaps whether there is another element to iterate over next). I think supporting backwards iteration through this mechanism is thus less important, but a language could theoretically construct a fat pointer which points to an element and the things to its left rather than to its right, and then iteration could be done the by doing subp which would do {addr-1,len-1}. It wouldn’t support going forwards and backwards randomly (unlesslenis just how many elements one wants to touch before stopping), but I’ve never used an iterator like that anyway and most iterators can’t do that anyway. If I were doing something that weird, I wouldn’t expect the benefit of operating directly on pointers, I’d have an index into an array. The point of allowing addp to work on 128 bit fields directly (on high-end Mills) is to make the machine wider in the most common case, and iterating forwards is by far the most common case. Of course, on Mills with less width and no 128-bit data paths, yeah, they will have to issue two ops and two drops on the belt to do each fat pointer operation. Also, in the case where reversed iteration is abstracted away: great! You can just do it in whatever way is most efficient for the Mill (at least in 99% of cases).

    I doubt anyone would want to garbage collect a Fat pointer that’s been modified by iteration (although one could, but it would take more bookkeeping and effort). E.g. in Zig when you deallocate you are expected to give back the full slice / fat pointer that was given to you by the allocator originally, without changes achievable by forward iteration (there is no blessed way to move a fat pointer backwards in Zig, you have to reconstruct it yourself). I think this problem currently is accounted for by most languages and the addp overloading idea I had doesn’t conflict with garbage collection whatsoever.

    Anyway, this is just an idea that I thought might be a nice optimization for high-end Mills to improve width and belt space in practice. Thank you for your consideration.

    • This reply was modified 1 year, 7 months ago by  Validark.
    • Ivan Godard
      Keymaster
      Post count: 689

      Quad (128-bit) is optional, transparent at the source language level. Forcing it to be mandatory would impact some attractive markets negatively. All descriptor operations can execute as discrete scalar ops just as well, and the scalar ALUs are useful for other things as well, which descriptor ops are not.

  • Validark
    Participant
    Post count: 21

    I am not suggesting that quad be mandatory, just that machines which do support quad could allow addp et al to work on quads in the way I’ve described. The specializer could break those up for lower-end Mills, couldn’t it?

You must be logged in to reply to this topic.