java - int vs float arithmetic efficiency in Java

Question

I'm writing an application that uses Dijkstra algorithm to find minimal paths in the graph. The weights of the nodes and edges in the graph are float numbers, so the algorithm doing many arithmetics on float numbers. Could I gain a running time improve if I convert all weight to ints? Is int arithmetic operations are faster in Java then float ones?

I tried to write a simple benchmark to check that out, but I'm not satisfied with the results I got. Possibly the compiler has optimized some parts of the program so the results doesn't looks good for me.

EDIT:

The problem I'm trying to solve is in the Information Retrieval field. The application should show answers to a query posed as a set of keywords.

My data structure is a weighted directed graph. Given a set of leaf nodes I have to find a smallest tree that connects these nodes and show the answer to the user. The weights are assigned by a weighting function based partially on the tf/idf technique. The user don't know what weights I assign to the nodes and edges he just wants to see answers relevant to the query he posed. So exact results are not required, just a possibility to enumerate answers according to theirs weights. Just the native use of weighting function (as I mentioned it is based on tf/idf) gives float weights so I used floats so far.

I hope this adds some background to the question.

score 2 · Accepted Answer

単純な操作の場合、intの方が高速ですが、intを使用すると、同じ結果を得るにはさらに多くの作業が必要になる場合があります。例えば

フロートとして

float f = 15 * 0.987;

intとして

int i = 15 * 987 / 1000;

余分な除算は、int演算に時間がかかる可能性があることを意味します。

score 1 · Accepted Answer

この種のことと同じように、パフォーマンスの目標を自分で設定してから、アプリのプロファイルを作成して、目標を満たしているかどうかを確認する必要があります。

多くの場合、驚くべき結果が得られることがあります。所要時間は基本数値タイプの影響をほとんど受けないこと、またはアルゴリズムが最適ではないこと。

そして、コンパイラの最適化に関しては、パフォーマンスの最適化の実際の有効な部分です。

タイプAを使用する方がタイプBを使用するよりも理論的に高速であるが、コンパイラーがタイプBを最適化して実際のシナリオでより高速にすることができる場合、それは失望の原因ではなく、貴重な証拠です。

score 1 · Accepted Answer

Integer subtractions are ~2.5 times faster than double subtractions, on my machine. Integer multiplications however, are only ~1.5 times faster than double multiplications.

The following test works on random data, which might prevent the compiler from optimizing.

// test whether int subs are faster than double subs
public void compareIntAndFloatSubtraction(){

    int N = 100000;  // input array size
    int k = 100000;  // number of mathematical operations performed on each element

    // generate random data
    int[] ints = new int[N];
    double[] doubles = new double[N];
    Random r = new Random(1l);
    for (int i = 0; i < N; i++) {
        ints[i] = r.nextInt();
        doubles[i] = r.nextDouble();
    }

    // measure integer subtractions
    long before = System.currentTimeMillis();
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < k; j++) {
            ints[i] -= ints[i-1];  // referring to another element might prevent from optimization also
        }
    }
    System.out.println(String.format("time needed for int subs [ms]: %s", System.currentTimeMillis()-before));

    // measure double subtractions
    before = System.currentTimeMillis();
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < k; j++) {
            doubles[i] -= doubles[i-1];
        }
    }
    System.out.println(String.format("time needed for double subs [ms]: %s", System.currentTimeMillis()-before));

}

score 0 · Accepted Answer

0

If you just want to compare weights, you should prefer int to float.

于 2010-07-28T08:30:56.857 に答える

score 0 · Accepted Answer

Generally you should not worry about a choice between int and float for performance reasons.

Here's an excerpt from the Appendix of Java Puzzlers:

Floating-point arithmetic is inexact. Don't use floating-point where exact results are required; instead, use an integral type or BigDecimal. Prefer double to float.

Unless you have a really good reason, you should generally prefer double to float if you must use floating point operation. If exact result is desired, then go ahead and use BigDecimal; it'll be slower since it's not a primitive, but unless profiling shows that it's not acceptable, this is often the best option.

If you must use floating point operation, then trying to optimize this by using int is ill-advised. This is likely to be a premature optimization and will only complicate the code unnecessary. Write it in the most natural, most readable way. Do not complicate your code unnecessarily for the sake of slight performance gains.

If you don't actually need floating point operation, then by all means use int or long instead.

score 0 · Accepted Answer

I think the performance is very much dependent on the algorithm and the platform the software is running on.

If you're doing matrix / array calculations on an X86 platform the runtime might optimize it to use SSE, which is a float/double only extended instruction set.

On other platforms the runtime might optimize to OpenCL (I don't believe anyone does that right now, but it might happen:). I have no clue what runs fastest on such a platform, and under what conditions. It may just be that OpenCL is optimized for an integer workload.

Under these circumstances I would conclude that it is not useful to optimize the data type (float or int) at this point, and just optimize the readability of the code.

If your code is highly performance critical, and you know exactly on which hardware the system will be running now and in the future, you could test typical workloads with various algorithms and select the one which best meets your needs.

But in general, just use an algorithm you can understand, keep the code readable, and thereby the bug count low. Fast code isn't worth that much if the results are not correct :)

score -6 · Accepted Answer

私はそうは思わない。

フロートは4バイトです。また、JavaのIntも4バイトです。

Date（java.util.Date）を使用して実行時間を取得してみませんか？

独自の100000ノードであるグラフを定義できます。次に、それを計算します。

java - int vs float arithmetic efficiency in Java

7 に答える 7

Related

Reference