Java does have JIT which supposedly generates some native code at run time. However, I find it hard to believe a highly suggestive and properly structured C code would underperform a Java code. Please compare your C code with a real compiler (e.g. icc). GCC is utter garbage when it comes to performance. Also, take advantage of C99 features (e.g. inline and restrict). Be as suggestive to the compiler as you can (e.g. use register qualifier where appropriate, order code to make vectorization more obvious..."neatness" and "style" have no meaning!). Also order your C code to mix as many operations as possible to reduce register pressure (compiler can generally do this). Finally, JIT probably takes advantage of processor-specific features (e.g. SSE for vectorization), please turn these features on when compiling the C code.
Why do you have to do this in C? Because C is complicated! The compiler cannot make too many assumptions. If you can, code the same program in Fortran and use ifort (again, GCC blows!). Fortran will probably blow both Java and C away because the language is so simple, the compiler can make more aggressive optimizations.