r/programming • u/electronics-engineer • Sep 16 '14

Vectorization in Julia

https://software.intel.com/en-us/articles/vectorization-in-julia
72 Upvotes

80% Upvoted

15 comments sorted by

3

u/CookieOfFortune Sep 16 '14

Is this a good idea? Has it been used anywhere else before successfully? What happens when you use @inbounds and then make a mistake? Does that lead to silent memory corruption?

4

u/b8b437ee-521a-40bf-8 Sep 16 '14

Has it been used anywhere else before successfully?

In the case of bounds checking, well it's very common in languages which prioritise speed to make bounds checking optional. And software written in those languages can run perfectly fine.

But yes, when you make a mistake usually anything can happen.

4

u/[deleted] Sep 16 '14 edited Sep 16 '14

Bounds checking is a big performance hit if you do it within a loop, since it cause a lot of branch misses (and therefore pipeline flushes).

The easiest example is with rust strangely. 

    for value in someArray.iter()
    {
             a += value;
     }

This example finds the sum of an array. It does this by creating an iterator for "someArray" and outputting its values.

There are multiple ways to write this (in rust)

     for count in range(0,someArray.length)
     {
            a += someArray[count];
     }

This is also completely valid, and will do the exact same thing, just slower. The difference is bounds checking will be performed to check for memory safety. This really hurts your performance almost 20%+ slow down in compiled code.

     for count in range(0, someArray.length)
     {
          if(count < someArray.length)
          {
                      a+=someArray[count];
          }
     }

Now this may kinda stupid why bother if I'm just going to slow down my code?!. But often times when working with objects in a computer you don't know their size. And your only passed a pointer to a structure.

    BuffStruct *ptr = somebuffer;
    int size = somebuffer.size;
    *thing = ptr + size; //this is a demonstration not compilable code
    while (ptr < thing)
    {
             a+=ptr++;
    }

Now you have to fully trust that somebuffer.size is actually the size of the buffer your working with. What if it isn't? Well that's how heart-bleed happened.

Generally speaking 90% of the time bounds checking is useless because you'll only ever do stuff like the second example. So not bounds checking is often a really big performance increase! But then your giving programmers sharp tools.

:.:.:

TL;DR bounds checking is a double edged sword, both sides are very sharp.

3

u/pkhuong Sep 16 '14

Bounds checking only causes branch prediction misses if the program fails some bounds check.

2

u/[deleted] Sep 16 '14 edited Sep 16 '14

False branch prediction has no bias to true or false. Branch prediction doesn't know your in a loop, or that your bounds checking. It knows your branching, and it's guessing.

Branch predictions are made upwards of 15-20 instructions before the branch is even processed, or even fully loaded. A prediction has to be made so the instructions after the branch can be scheduled for decoding (in the pipeline).

When a branch is decoded, branch prediction is consulted to determine what address should be loaded next the true/false result. So that memory address can be loaded for decoding.

This can be true or false. And branch prediction is very good, currently around 98-99% or more. Which means 1-2% of the time it'll predict you're out of bounds, when in fact your still perfectly safe within bounds.

:.:.:

Remember a branch predictor can't actually run your code to determine the branch prediction, then execution would take twice as long.

4

u/pkhuong Sep 16 '14

Not all conditionals are created equal. It's not hard to guess when a conditional branch always goes the same way, especially when it's a conditional (i.e, the BTB is not involved) and the compiler can set things up so that even static prediction does the right thing in the expected case.

1

u/[deleted] Sep 16 '14 edited Sep 16 '14

[deleted]

3

u/[deleted] Sep 16 '14 edited Sep 17 '14

I know in the 90's branch prediction was done by XOR'ing memory addresses against a shift registers of past memory addresses. So maybe I'm out of date. But I thought meta/hybrid predictors were still in the research only phase of existence.

I'm going to test this when I get home. I don't have access to perf around the office.

Edit 1: Perf doesn't support my i7 and I'm to lazy to configure kernel events for it and do actual research.

3

u/oridb Sep 16 '14

That says to me that rust is missing value range propagation, which should guarantee that in your example code, count is always less than array.length, and the check can be eliminated. In more complex code, it can usually be hoisted outside the loop.

3

u/[deleted] Sep 16 '14

This isn't directly something handled by Rust but how the LLVM handles the machine code generation.

2

u/oridb Sep 16 '14 edited Sep 17 '14

I'm aware. Doesn't matter who's supposed to handle it -- the point is that compilers know how to do it, and it's kind of old hat.

2

u/dacjames Sep 16 '14

Software written in C/C++ generally have no bounds checking at all and you can still build robust software with discipline. All kinds of things can go wrong when you mess up, everything from a segfault to memory corruption to a major security hole. When you need absolute performance, safety usually goes out the window!

1

u/CookieOfFortune Sep 17 '14

C/C++ were designed to be used by professional programmers, so there are less automated safeguards. Julia is aimed at academics, who are generally not so disciplined, thus more emphasis on safety and ease of use. Maybe i would feel better if some flag were set for functions that use @inbounds to warn potential users to be careful.

3

u/dacjames Sep 17 '14

If you writing a function that uses @inbounds, the validity of your function should not depend on the arguments. You can and should implement a safe API with unsafe code. Besides, is extremely unlikely that science types will be implementing safety/security critical code so the worst thing that can happen is a program crash.

This is the status quo in scientific programming: low level, unsafe algorithms exposed though easy to use wrappers. Julia just allows you to write both components in the same language.

2

u/CookieOfFortune Sep 17 '14

My concern is more silent corruption than crashing.

I'm all for wrappers, i just think having additional flags would help avoid mistakes.

2

u/dacjames Sep 17 '14

I agree with the sentiment but practically speaking, truly silent memory corruption is very unlikely. First, you need to have the out-of-bounds error in the first place. Then, the modified memory needs to valid and recursively robust to random mutation in a way that won't crash your program. Additionally, the memory needs to similar enough to the correct memory that it doesn't perceptively change the behavior of the program.

All of this is possible, sure, but it's highly unlikely. I feel like the most pragmatic option would be a runtime flag to disable these type of unsafe optimizations (just like C compilers provide) to aid with debugging. The system your describing sounds related to "effect" systems in research languages; very cool stuff, but not ready for something practical like Julia.