Začátky v Javě

[r]

http://www.azulsystems.com/technology/c4-garbage-collector

The C4 (Continuously Concurrent Compacting Collector) is an updated generational form of the Azul Pauseless GC Algorithm and is the default collector of Zing®. C4 differentiates itself from other generational garbage collectors by supporting simultaneous - generational concurrency: the different generations are collected using concurrent (non stop-the-world) mechanisms that can be simultaneously and independently active. Unlike other algorithms, it is not ‘mostly’ concurrent, but fully concurrent, so it never falls back to a stop-the-world compaction.

[Reklama]

[Kolemjdoucí]

http://www.azulsystems.com/technology/c4-garbage-collector

Máte s tím nějakou zkušenost? To že si to výrobce sám chválí aby získal platící zákazníky je očekávatelné a nemá to vlastně žádnou vypovídací hodnotu...

[Jakub Galgonek]

Tak tady je ten program: http://uloz.to/xbxoSz7K/shortestpath-zip.
Rychlost běhu programu je od 1000 ms až do 1200 ms.

Tak jsem také něco zkusil:

time ./shortestPath (g++ 4.7.3)
real    0m0.784s
user    0m0.683s
sys     0m0.103s

time ./shortestPath (icc)
real    0m0.912s
user    0m0.800s
sys     0m0.110s

time java test/Dijkstra
real    0m0.408s
user    0m0.413s
sys     0m0.017s

[...]

Java na tom vlastně není vůbec špatně, když většina její kritiky pramení z neznalosti.

Kritika všeho pramení obvykle z neznalosti. Pak je problém, když je založená na znalostech a zkušenostech a naváží se do ní trotli...

oba vas mam na blacklistu, jako troly, ale tentokrat udelam vyjimku.
1. historie projektu
2. porizovaci a provozni naklady realtime jvm
3. kapacita realtime jvm
4. cena integrace a zmeny licence nekompatibilni zmeny kernelu od dodavatele realtime jvm, kdyz uz i tak kernelari cast jadra vyhazuji formou vypnutych voleb a odpatchovanim zdrzovaciho bloatware v nekterych funkcich a to promile jaderneho rozhranni co je kriticke forknou a napisou zbrusu jinak.

[Jakub Galgonek]

Kód: [Vybrat]

import java.util.Random;


public class Dijkstra
{
    public static int compute(final int count, int start, int stop, final int weight[])
    {
        boolean[] invalid = new boolean[count];
        int distance[] = new int[count];
       
        for(int i = 0; i < count; i++)
            distance[i] = Integer.MAX_VALUE;
       
        int u = start;
        distance[u] = 0;
       
        while(u != stop)
        {
            invalid[u] = true;
           
            int minDistance = distance[u];
            int min = Integer.MAX_VALUE;
           
            for(int v = 0; v < count; v++)
            {
                if(invalid[v])
                    continue;
               
                int distanceThroughU = minDistance + weight[u * count + v];
               
                if(distanceThroughU < distance[v])
                    distance[v] = distanceThroughU;
               
                if(distance[v] < min)
                {
                    u = v;
                    min = distance[v];
                }
            }
        }
       
        return distance[u];
    }
   
   
    public static void main(String[] args)
    {
        long time = System.currentTimeMillis();
       
        final int count = 5000;
        final Random rand = new Random();
       
       
        int weight[] = new int[count * count];
       
        for(int i = 0; i < count * count; i++)
            weight[i] = rand.nextInt(100) + 1;
       
        int res = compute(count, 0, count - 1, weight);
       
        time = System.currentTimeMillis() - time;
        System.out.println("result: " + res);
        System.out.println("time  : " + time);
    }
}


[Reklama]

[DK]

Pokud potřebujete systém s garantovanou maximální latencí, nemůžete vzít běžný OS, ale musíte použít realtime OS. Úplně stejně nemůžete použít běžnou desktopovou Javu od Oracle, ale musíte použít realtime JVM. Stop-the-world na potenciálně neomezenou dobu totiž není principiální vlastnost GC, je to vlastnost pouze některých implementací.

Java na tom vlastně není vůbec špatně, když většina její kritiky pramení z neznalosti.

Jenom bych dodal, ze je treba taky pouzit "odlisne" struktury, nez standartni, ktere maji vysokou rezii (obzvlaste kolekce a mapy, coz resi treba Javolution)

[gamer]

Jakub Galgonek: RAII si těžce naběhl tím, že vygeneroval graf, který má velký počet hrah (V^2). Tím způsobil, že standardní dijkstra algoritmy využívající priorotní frontu jsou pomalejší, protože mají režii navíc v prioritní frontě. Kdyby RAII nebyl hloupý a přečetl si tohle:
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Running_time
Dozvěděl by se že:
For sparse graphs, that is, graphs with far fewer than O(|V|^2) edges, Dijkstra's algorithm can be implemented more efficiently by storing the graph in the form of adjacency lists and using a self-balancing binary search tree, binary heap, pairing heap, or Fibonacci heap as a priority queue to implement extracting minimum efficiently.
Takže "naivní" implementace dijkstry bez prioritní fronty bude pro RAIIův graf rychlejší.

[Jakub Galgonek]

Jakub Galgonek: RAII si těžce naběhl tím, že vygeneroval graf, který má velký počet hrah (V^2).

Já vím, proto jsem se také Fibonacciho haldě vyhnul. Když je spojené každé město s každým, je to naprosto zbytečná režie.

RAII tím ale (asi nechtěně) ukázal jednu pěknou věc. Spoustu lidí upřednostní Javu před C++, protože vývoj v ní je rychlejší a pohodlnější. Je zde méně věcí, na které je třeba si dát pozor, méně možností, jak se střelit do nohy. Ale zaplatí se za to nějakou tou ztrátou rychlosti. No a RAII, který tu tak volá po rychlosti, nyní udělal něco podobného. Zvolil obecnou knihovnu, asi aby si ušetřil práci a měl to rychle hotovo, a zaplatil za to horší rychlostí.

Mimochodem, Filip ho varoval:

daleko větší dopad má třeba zvolený algoritmus.

[JSH]

RAII tím ale (asi nechtěně) ukázal jednu pěknou věc.

RAII tady opakovaně ukazuje, jaké má mezery v chápání, proč něco běží pomalu. Přijde mi jako typ, který je schopný pilovat superefektivní bubblesort a dokonale přehlížet "nedůležité" věci jako je asymptotická složitost, nebo posloupnost přístupů do paměti.

[perceptron]

este pre zboja a python rest

https://gist.github.com/anonymous/9933517

[majo33]

C++ verzia (dufam ze tam nemam chybu):

Kód: [Vybrat]

#include <vector>
#include <limits>
#include <chrono>
#include <iostream>
#include <cstdlib>


const int INT_MAX = std::numeric_limits<int>::max();

int compute (int count, int start, int stop, const std::vector<int> &weight)
{
  std::vector<bool> invalid(count, false);
  std::vector<int> distance(count, INT_MAX);
       
  int u = start;
  distance[u] = 0;
       
  while(u != stop) {
    invalid[u] = true;
           
    int minDistance = distance[u];
    int min = INT_MAX;
           
    for (int v = 0; v < count; ++v) {
      if (invalid[v]) {
        continue;
      }
               
      int distanceThroughU = minDistance + weight[u * count + v];
               
      if (distanceThroughU < distance[v]) {
        distance[v] = distanceThroughU;
      }
               
      if (distance[v] < min) {
        u = v;
        min = distance[v];
      }
    }
  }
       
  return distance[u];
}

int main(int argc, char **argv)
{
  auto start = std::chrono::high_resolution_clock::now();

  const int COUNT = 5000;
  std::vector<int> weight(COUNT * COUNT);
  srand(time(0));

  for (int i = 0; i < COUNT * COUNT; ++i) {
    weight[i] = (random() % 100) + 1;
  }       

  int res = compute(COUNT, 0, COUNT - 1, weight);

  auto end = std::chrono::high_resolution_clock::now();

  int duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
  std::cout << "result: " << res << std::endl;
  std::cout << "time  : " << duration << std::endl;
       
  return 0;
}

Casy (priemer 50 spusteni, prvy stlpec je vypis casu s programu, druhy s programu time):

Java : 479ms, real 561ms
G++  : 373ms, real 384ms
Clang: 362ms, real 376ms

Java verziu som spustal len prikazom time java Dijkstra, mozno by to poladil nejaky parameter?
C++ verzie su kompilovane prikazmi (medzi -O2 a -O3 nieje podstatny rozdiel):

g++ -std=c++11 -O2 Dijkstra.cpp -o Dijkstra_gcc
clang++ -std=c++11 -O2 Dijkstra.cpp -o Dijkstra_clang

[RAII]

Mno, jak vidno, posral sem to. Poznámka pro majo33. Když použiješ release mód (při kompilování tvé C++ verze), dostaneš se na 330 ms. 380 ms máš s debug módem.

[Jakub Galgonek]

Java verziu som spustal len prikazom time java Dijkstra

Jakou jsi použil Javu?

[Jakub Galgonek]

Poznámka pro majo33. Když použiješ release mód (při kompilování tvé C++ verze), dostaneš se na 330 ms. 380 ms máš s debug módem.

Když se kouknu do tvého shortestPath.cbp, co u tebe znamená release mód, pak musím konstatovat, že majo33 release mód použil.

[RAII]

nepoužil ... s ním mi vyšel stejný (+-10) čas jako tam napsal (384) ... bez něj 330 ms