Item — HN Reader

It's worse than that. It's still problematic to even assume SSE4.2, not to mention AVX2, which would help significantly. Virtualization is making the problem worse, because hypervisors set CPUID bits to lowest common denominator within a vMotion / teleportation domain.

I think (specialized) JITting is the answer for that. Generate code on the fly. I've been lately playing around with JITted [de]serializers, etc. I think it might be possible to have an order of magnitude gains in JSON, XML, msgpack, etc. processing.

Even *printf can be much, much faster. If the format specifier is static, first run just generates code just for that specifier. Subsequent invocations can be about 10-20x faster versus normal style format string scanner.

Edit: When I say JIT, I'm not talking about JVM or any other mainstream implementation specifically, but the concept in general. Which means just-in-time generation of (optimal) machine specific code.

4 comments

> Even *printf can be much, much faster. If the format specifier is static, first run just generates code just for that specifier.

There's no reason you can't do what you want today AOT in stronger languages. Adding a JIT, or special AOT treatment of any given set of functions, to workaround weaknesses in C and its poor standard library, is just sad. Another problem is that stock libc printf has to be able to deal with localisation, and locales can be changed arbitrarily at runtime (although it's not thread-safe to do so)

One way to get all the performance out of modern hardware would be to stop using languages and libraries that haven't seen major improvement since the 90s, and still can't deliver optimal execution of functions, like printf, designed in the 60s.

Cough existing codebase cough.

We can significantly boost performance for some aspects of C/C++ in the meanwhile by JITting. "sprintf" is just slow. (side note: Also C++ "<<" stream implementations I've seen are unbelievably slow (about 3x slower than *printf) and tend to have a lot of side effects, such as a barrage of system calls if unbuffered -- the 99% case. Although I'm sure this is fixable with a better stream implementation and maybe some compiler assistance. Just try to benchmark stringstream...)

Otherwise I agree with you of course. Time is up for C/C++. Although I think they'll stay around. They're just not a good fit for modern CPUs anymore. There just isn't a good replacement yet. Maybe Rust will be that one day?

The problem with C isn't that it's old, unsafe, conservative, or that it lacks GC. The problem is that people have religious wars about strncat vs strlcat, which are both terrible and both equally broken, rather than looking at the big picture. The big picture is that there are hardly any functions in the standard library that aren't terrible.

If you wanted a safe, fast printf function in C for example, one way to do it would be to provide a function that took a format string and returned a reusable handle, much like you use regular expressions in a library like PCRE. This would give you instant benefits when it came to print and scan loops (no re-parsing of the format string), while still giving the compiler ample opportunity to do type checking without too much work. It even opens the door to a JIT and/or AOT backend, all without major changes to the actual compiler.

    void (*hello)(char const*, int);
    if (!printf_jit ("Hello %s, you have %d points\n", &hello)) {
        /* jit failed */
    }
    hello ("Steve", 80);
    printf_free (hello);

I don't lump C++ in the same boat. The above code can be written semantically in C++ today, without any external libraries, with full type-checking.

Nice idea how to get type checking. I was thinking more of a macro that initializes a function pointer with a code generator and subsequently overwrites it once JIT has been completed.

Sadly in both cases, no chance to inline or avoid unneeded stack use. Sadly the parameter string ("Steve") needs to be scanned for zero terminator -- this is slow. Zero terminated strings are an evil invention.

Is there any reason that it has to be just-in-time? Maybe there is potential for ahead-of-time SIMD optimization of precompiled binaries. There would be lots of tricky details, but perhaps an "sufficiently intelligent" installer could scan for SIMD optimizations and patch at install time.

Or maybe this could be built into the CPU cache? We already have a 1000-plus opcode decoded instruction cache. Already certain 'idioms' are optimized at decode time. How impossible would it be to have an opcode optimizer that rewrites the instructions in the cache to use the widest vector instructions available?

Currently CPU capabilities can even change on the fly, because of virtualization technologies like vMotion. That's why CPUID flags need to be masked by the hypervisors to hide CPU features that some CPUs in the same domain don't have.

Maybe that is possible. But would it be simpler? Maybe it can be a part of the solution?

Why would you care? You can generate a lot of code in a microsecond.

> Or maybe this could be built into the CPU cache? We already have a 1000-plus opcode decoded instruction cache. Already certain 'idioms' are optimized at decode time. How impossible would it be to have an opcode optimizer that rewrites the instructions in the cache to use the widest vector instructions available?

Sorry, but I don't understand your question.

Why would you care? You can generate a lot of code in a microsecond.

Because the limiting factor isn't code generation speed, but pattern recognition. Also, having spent too much time staring the mangled junk produced by optimizing compilers that concentrate on speed of compilation, I'm naively hoping that dedicating more processor time to optimizations will produce better code.

Sorry, but I don't understand your question.

CPU's no longer decode x64 instructions for tight loops. Instead, they inject decoded opcodes by that they index by starting address. Already, simple optimizations are being made at this level: https://sites.google.com/site/paulclaytonplace/andy-glew-s-c...

I'm wondering how feasible it would be to "rewrite" series of scalar instructions to a smaller number of SIMD alternatives either as part of the front end decoder or as something that continually optimizes the stream of opcodes in the cache.

> Because the limiting factor isn't code generation speed, but pattern recognition. Also, having spent too much time staring the mangled junk produced by optimizing compilers that concentrate on speed of compilation, I'm naively hoping that dedicating more processor time to optimizations will produce better code.

You wouldn't need to care of the actual generated code. It would be generated just and only for the currently running processor and memory subsystem.

> I'm wondering how feasible it would be to "rewrite" series of scalar instructions to a smaller number of SIMD alternatives either as part of the front end decoder or as something that continually optimizes the stream of opcodes in the cache.

Right. First you'd need to have available instruction encodings -- for x86, they're in very short supply. Secondly this would increase the amount of state that needs to be stored to memory and restored when context switching between threads and processes, unless the support would only be available to the operating system and opcodes are shared by all thread contexts.

You can achieve this by JITting already, without the context switching overhead.

On the positive side, this would ease instruction cache pressure.

I don't think we're talking about the same thing. I'm probably not helping by being sloppy distinguishing between opcodes and µops. But I'm referring to the hardware decoded µop cache that mostly replaced the "loop stream detector" in Intel processors post-Nehalem. No context switching, no OS support, rather hardware optimizations targeted at the interface between the outward facing x64 (CISC) instruction set and the post-encoding (RISC) µop driven monster within.

It would be a box along the same path as the one labelled "uOP Cache Hit Logic": http://pc.watch.impress.co.jp/video/pcw/docs/601/851/p16.pdf

I think that's what the SIMD instructions largely do. Like AVX-512 when talking about Skylake. A more direct interface to the "monster within". The monster got bigger, so there's a need to feed it with bigger chunks of work.

µops are just an intermediary translation format. The point in JITting is to have the CPU translating the intent better to actual µops.

I guess the other solution is to use OpenCL and write all kernels in that language. Then it should JIT into AVX-512 if it is available.

It might be acceptable for some subset of "embarrassingly parallel" problems. For other problems, writing OpenCL code that even approaches hardware potential is very hard. We might need other intermediary languages than it.

Currently LLVM is a better fit than OpenCL in general.

If you want the last 50% of performance, hand coding seems to be unfortunately the only way. Very little code needs to be that fast, though.

JIT and AOT on-device is the future, I agree. How good are the JVMs at taking advantage of new instructions?

When I talk about JIT, I think primarily specialized form of them.

I don't see much potential in JVM in its current form to be able to take advantage of this. Currently pattern detection and intrinsics ('fake' method invocation that is translated to just 1-3 instructions) are possible.

JVMs should especially offer better control over data memory layout. Number of references (pointers) required needs to be radically reduced. Objects should form continuous memory regions, and have a minimal number of references to elsewhere in memory. Inlining should be used as much as practical instead of pointer chasing. Unions would help too with vectorization, but would understandably significantly complicate the optimizer.

For example, an empty or a short String should be just 16 object-inlined bytes. Larger ones could still of course have references to byte or char arrays. UTF-16 should be removed in favor of UTF-8.

My understanding is that JVMs do not generate any advanced instructions from standard Java code. The only time they use these instructions is if they link in hand coded C++ libraries that make use of them.

Edit: Stackoverflow answer says that in rare cases the JVM can vectorize simple loops: http://stackoverflow.com/questions/10784951/do-any-jvms-jit-...

Just take a look at the code they generate, it's easy. In short, they do generate SIMD code, but very rarely take advantage of vectorized execution.

Why aren't the processor manufacturers making their own JITs and AOT compilers? Surely that would be a competitive advantage.

Intel makes a famous AOT compiler, ICC. https://software.intel.com/en-us/intel-compilers

Yes, but it's for developer-compiled languages. It's not like I switch from an AMD to an Intel processor and suddenly all C code on my machine has new instructions in them. Compiled code remains the way it is.

This is not what I want. What I want is either JIT or AOT-on-end-device.

Binary (compiled code) JIT compilation could very well be faster than direct execution.

I'm not aware of anyone currently using these techniques for running native code faster. Yet.

You can also call these techniques binary translation if you like.

At simplest level, one could for example dynamically replace relevant static library calls with higher performance versions. Perform function signature based optimization - when a certain known common function is found, simply replace it with a faster version.

More advanced ones could for example inline functions, even those pointed by function pointers given a guard condition. It could also vectorize suitable serial code.

Superoptimization techniques could also be applied to the instruction stream. http://en.wikipedia.org/wiki/Superoptimization

Even complex optimizations are possible. Like memory access pattern translation. The JIT compiler could perform cache simulation and find a mapping between memory accesses that would increase true hardware level locality of reference. Performance could be improved by generating access transformation code when target binary tries to access memory. Like map image processing memory access code from row major to Z-order curve to increase cache hit probability. Unless memory mapped (either to other processes or physical hardware) the buffer resides the data would need to be translated back row-major only for system calls. A lazy page fault mechanism could also work in some cases.