C++ ssie pałke.

Proponuje mały test:
Program C++:

#include <map>
#include <cstdio>
int main() {
   std::map<int, int> m;
   for(int i = 0; i < 3000000; ++i) {
      m[i] = std::rand();
   }
   for(int i = 0; i < 10; ++i) {
      printf("%d", m[rand() % 3000000]);
   }
   return 0;
}

Program Java:

import java.util.TreeMap;
import java.util.Random;

public class FuckCpp {
	public static void main(String[] args) {
		TreeMap m = new TreeMap();
		Random r = new Random();
		for(int i = 0; i < 3000000; i++) {
			m.put(i, r.nextInt());
		}
		for(int i = 0; i < 10; i++) {
			System.out.println(m.get(r.nextInt(3000000)));
		}
	}
}

Program w C++ nie raczy się skończyć, program Java śmiga nawet bez wielkich optymalizacji.
Kod C++ skompilowany pod VS2008.
Kod Java skompilowany JVM6
Co ciekawe to nie alokacja zajmuje tyle czasu w C++ tylko dealokacja...
Na gcc było lepiej, przynajmniej program się skończył...

Spróbuj użyć jakiegoś normalnego randoma, a nie tych wbudowanych. Np MersenneTwister.

To akurat nie kwestia randoma. Cały program w C++ wykonuje się szybko. Problem jest przy return 0 gdy włącza się destruktor mapy. Nawiasem mówiąc żeby to stwierdzić musiałem użyć debuggera z widokiem na asm... (już myślałem że gdzieś sobie adres powrotu nadpisałem i wpadło mi w nieskończoną pętlę, ale niee).
Ciekawe ile z zaciętych fanboyów C++ o tym wie. Ile z nich pisze własne alokatory, żeby zapobiec problemowi.
A pewnie najgłośniej krzyczą, że java jest taka wolnaaa.

Kompilacja w trybie debug (zwłaszcza połączona z aktywnym debugowaniem) wymusza kosztowne monitorowanie alokacji i spójności sterty, która jest weryfikowana przy każdej dealokacji. Kompilacja w trybie realease, puszczona wolno, jest tego narzutu pozbawiona. To przecież informacje znajdujące się w dokumentacji środowiska.

Java jest po prostu "inna". W większości sytuacji jest wolniejsza, ale zdarzają się sytuacje, w których jest szybsza, już na kilka takich trafiłem. Optymalizacje czasem są wydajniejsze, java częściej pomija bezsensowne pętle, tak mi się wydaje przynajmniej.

Ogólnie rzecz biorąc na dzisiejszych PCtach nie trzeba się przejmować tym ubytkiem prędkości spowodowanym przez JVM. Chyba że piszemy jakieś raytracery

Co do tego przykładu: u mnie (ubu 10.04, GCC 4.4, parametr -O2) dealokacja jest dość szybka, najdłużej losowanie i uzupełnianie mapy. Całość 2.3s.
Natomiast Java 1.6_u24 bodajże z tym przykładem radzi sobie u mnie w ok. 6 sekund, z tym, że dealokacja jest niezauważalna, 99,9% czasu to losowanie.

SAM SSIESZ PAUKE napisał(a)

Kompilacja w trybie debug (zwłaszcza połączona z aktywnym debugowaniem) wymusza kosztowne monitorowanie alokacji i spójności sterty, która jest weryfikowana przy każdej dealokacji. Kompilacja w trybie realease, puszczona wolno, jest tego narzutu pozbawiona. To przecież informacje znajdujące się w dokumentacji środowiska.

Zapomniałem dodać, że kompilowane było oczywiście w trybie Release. Polecam sprawdzić na VS2008. Chętnie się dowiem, czy na VS2010 jest taka sama kicha (akurat nie mam licencji).

Ideone.com (gcc-4.3.4) 1.69 sekundy
Ideone.com (gcc-4.5.1) 1.64 sekundy
kiedyś mnię wyjszło, że dostaję czas na procku 2.6 GHz
(troszkę szybciej, 1.46 sek gdy pierwsza pętla zaiwania od max do zera, ma to sens)

@Xitami: Ale właśnie abecadlo... mówił, że na gcc jakoś idzie.
VS2010 Release: 5s
VS2010 Debug: 69s

a sprawdź proszę gdy zamiast
for(int i = 0; i < 3000000; ++i) {
dasz
for(int i=3000000-1; i>0; --i) {

(troszkę szybciej, 1.46 sek gdy pierwsza pętla zaiwania od max do zera, ma to sens)

A czemu ma to sens?

Release 5s (zmiana niewielka)
Debug 62s

Dla mnie ma to sens taki sam, jak załatwianie pierwszego z kolejki zamiast za każdym razem latanie do ostatniego

Spróbuję swojej teorii na podstawie kodu z headerów VS2010. Podczas linijki m[i] = ... następuje odwołanie do funkcji _Insert z pliku xtree:

iterator _Insert(const_iterator _Where,
		_Nodeptr _Node)
		{	// try to insert node at _Node using _Where as a hint
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (_Where._Getcont() != this)
			_DEBUG_ERROR("map/set insert iterator outside range");
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

		const value_type& _Val = this->_Myval(_Node);

		const_iterator _Next;
		bool _Leftish = false;	// assume nearest point is end of sequence

		if (size() == 0)
			return (_Insert(true, this->_Myhead, _Node));	// empty tree
		else if (this->_Multi)
			{	// insert even if duplicate
			if (_Where == begin())  /*Pierwsze sprawdzenie: czy wstawić element na początku*/
				{	// insert at beginning if before first element
				if (!_DEBUG_LT_PRED(this->comp,
					this->_Key(_Where._Mynode()), this->_Kfn(_Val)))
					return (_Insert(true, _Where._Mynode(), _Node));
				_Leftish = true;	// nearest point is beginning of sequence
				}
			else if (_Where == end()) /*Drugie sprawdzenie: czy wstawić element na końcu*/
				{	// insert at end if after last element
				if (!_DEBUG_LT_PRED(this->comp,
					this->_Kfn(_Val), this->_Key(_Rmost())))
					return (_Insert(false, _Rmost(), _Node));
				}
			/* ..... */
			}
		else
			{	// insert only if unique
			if (_Where == begin())   /* Tak samo - pierwsze sprawdzenie, czy na początek */
				{	// insert at beginning if before first element
				if (_DEBUG_LT_PRED(this->comp,
					this->_Kfn(_Val), this->_Key(_Where._Mynode())))
					return (_Insert(true, _Where._Mynode(), _Node));
				}
			else if (_Where == end())   /* Drugie sprawdzenie, czy na koniec */
				{	// insert at end if after last element
				if (_DEBUG_LT_PRED(this->comp,
					this->_Key(_Rmost()), this->_Kfn(_Val)))
					return (_Insert(false, _Rmost(), _Node));
				}
			/* ... */
			}
		/* ... */
		}

Rozpatruję dwa przypadki: kiedy nasza wartość i wzrasta, kolejne elementy trafiają na koniec. Wtedy na pewno zostaną wywołane funkcje begin() oraz end(), a także dwa porównania iteratorów (_Where == begin() albo end()). Weźmy program:

#include <map>
#include <cstdio>
#include <windows.h>
#define DECREMENT
int main() {
    std::map<int, int> m;
    for(int i = 50000; i >= 0; --i) m[i] = std::rand(); /* Wypełnianie */
    int u = GetTickCount();
    /*Iterator nocomp tworzę po to, by zasymulować porównanie*/
    std::map<int, int>::const_iterator nocomp = m.begin(); nocomp++;
    std::map<int, int>::iterator it;
    for(int i = 0; i < 3000000; ++i){  /*Symulacja 3000000 wstawień*/
        it = m.begin();
        if(it == nocomp) printf("1");
#ifndef DECREMENT
	it = m.end();
	if(it == nocomp) printf("2");
#endif
    }
    printf("Czas: %ims\n", GetTickCount()-u);
}

Ponieważ zdefiniowaliśmy etykietę DECREMENT, linijki pomiędzy #ifndef i #endif nie wykonają się. Średni czas wykonania programu (3 powtórzenia) wynosi u mnie 3588ms. Zakomentowujemy linijkę #define DECREMENT i teraz dwie wspomniane linijki wykonają się. Średni czas: 7030ms (taaaak! mniej więcej dwukrotnie więcej). Czas wzrósł o ok. 3,5s. Pozostało jeszcze kilka sekund różnicy. Być może właściwe wstawianie na koniec jest powolne, być może to błąd statystyczny :/

Nie wiem, czy się nie okaże, że to wszystko jest "do kitu", ale myślę, że jest OK.

Xitami ma rację - ten dodatkowy narzut wynika z właściwości drzewa binarnego. Przy wstawianiu w kolejności rosnącej trzeba przy każdym wstawieniu zrobić log(n) porównanań oraz iteracji przez drzewa (n - ilość elementów w drzewie). Przy kolejności malejące trzeba zrobić tylko jedno porównania i żadnych iteracji.
Jeszcze pozostaje kwestia rotacji bo map to drzewo czerwono-czarne, ale nie chce mi się grzebać jak to działało ;p

Nadal nie rozumiem, czemu wstawianie malejąco ma być szybsze. Przecież drzewo nie jest stale asymetryczne, tzn chyba nie wymuszają scenariusza, w którym ścieżka do najmniejszego elementu jest zawsze znacząco krótsza niż ścieżka do największego.

Jedyne sensowne wytłumaczenie to dla mnie scenariusz, w którym map trzyma w środku wskaźnik do węzła z najmniejszą wartością (ale do tego z największą już nie) i dzięki temu nie traci log(n) kroków za każdym razem na wyszukiwanie kluczy przy wstawianiu malejąco.

Edit:
Chociaż begin() i rbegin() muszą mieć czas stały, więc map musi trzymać w środku wskaźniki do skrajnych węzłów po obu stronach. W takim razie może np przy dodawaniu elementu jest taki kod:

if (nowyElement <= najmniejszy) {
  ...
} else if (nowyElement < największy) {
  ...
} else {
  // nowyElement >= największy
  ...
}

I w tym przypadku dostanie się do pierwszego ifa jest szybsze.

@Wibowit: właśnie tak działający kod z VS podrzuciłem kilka postów temu. Popatrz na linijki:

if (_Where == begin())
{ // insert at beginning if before first element
  // .....
}
else if (_Where == end())
{ // insert at end if after last element
  // .....
}
// .....

A w bibliotece VS, jak sprawdziłem, procedury begin() i end() zwracające iteratory do początku lub końca mapy, mają najprawdopodobniej złożoność O(1), czyli gdzieś musi być zapisana informacja o początku/końcu.

abecadlo_z_piekła napisał(a)

SAM SSIESZ PAUKE napisał(a)

Kompilacja w trybie debug (zwłaszcza połączona z aktywnym debugowaniem) wymusza kosztowne monitorowanie alokacji i spójności sterty, która jest weryfikowana przy każdej dealokacji. Kompilacja w trybie realease, puszczona wolno, jest tego narzutu pozbawiona. To przecież informacje znajdujące się w dokumentacji środowiska.

Zapomniałem dodać, że kompilowane było oczywiście w trybie Release. Polecam sprawdzić na VS2008. Chętnie się dowiem, czy na VS2010 jest taka sama kicha (akurat nie mam licencji).

To jeszcze z łaski swej odpal program poza kontrolą debuggera. U mnie na VS2005 średni czas to 6 sekund (liczone razem z czyszczeniem mapy), podobnie na MinGW. W Javie wyszło średnio 2.3 sekundy, tyle że tu odpada czas potrzebny na zwolnienie pamięci.

Tytuł z d**y wzięty.

Na ideone:
http://ideone.com/A4Os2 - 1.65s (C++)
http://ideone.com/XsRvV - 3.04s (Java) i skończył się sterta, więc program się posypał...

O tym myślałem mówiąc o sensie.
Ideone 1.25

#include <map>
#include <cstdlib>
#include <cstdio>
int main() {
   std::map<int, int> m;
   int j=0;
   for(int i = 0; i < 3000000; ++i) {
      m[j] = rand(); 
      j+=2099963; if(j>=3000000) j-=3000000;
   }
   for(int i = 0; i < 10; ++i) {
      printf("%d", m[rand() % 3000000]);
   }
   return 0;
}

(Java) i skończył się sterta, więc program się posypał...

Takie przydzielanie pamięci w Cpp to też chu*nia bo dla każdej pary 8 bitowej jest przydzielanae 4/8 bajtów na rozmiar bloku.
Więc że na IdeOne jest mały limit dla sterty Javy wcale nie znaczy, że program w cpp bierze mniej.

Drodzy javovcy!

Przeciez 99% z was nie wie czym sie rozni pointer od referencji... Te wasze wypociny nazywacie programowaniem? Powaznie?

Akurat referencje Javowe mają inną semantykę od referencji i wskaźników C++owych. Kto by sobie głowę zwracał takim durnym językiem jak C++?

Wibowit napisał(a)

Akurat referencje Javowe mają inną semantykę od referencji i wskaźników C++owych. Kto by sobie głowę zwracał takim durnym językiem jak C++?

Nie mów do egona tak skomplikowanym językiem bo mu głowa wybuchnie.
http://www.yoda.arachsys.com/java/passing.html napisane przez Javowca.

0x200x20 napisał(a)

Wibowit napisał(a)

Akurat referencje Javowe mają inną semantykę od referencji i wskaźników C++owych. Kto by sobie głowę zwracał takim durnym językiem jak C++?

Nie mów do egona tak skomplikowanym językiem bo mu głowa wybuchnie.
http://www.yoda.arachsys.com/java/passing.html napisane przez Javowca.

W sumie to samo jest w C++ - też wszytko jest przekazywane przez wartość, ale C++ daje po prostu większą dowolność: przekazywanie obiektu, wskaźnika, referencji. Właśnie m.in. to ograniczenie w javie na początku mnie od niej odrzuciło(plus parę innych kwestii), na szczęście w dalszej perspektywie to nie przeszkadza.

Trzeba przyznać, że biblioteka standardowa Javy, a C++ to jak niebo, a ziemia.

Ogólnie tego typu dyskusje są bez sensu. Każdy woli język, który zna lepiej, a przecież nie o to chodzi. Wybór języka zależy od tego co się chce zrobić i tyle, bez żadnej filozofii, teologii czy innego fanatyzmu ;)