Jak działa nasz silnik symulacji?
Nasz silnik symulacji jest oparty na technice Discrete Event Simulation. Nie iteruje po sekundach — przeskakuje do momentów gdy dzieje się coś istotnego.
1. Czym jest DES?
Discrete Event Simulation to technika modelowania systemów, w których stan zmienia się w dyskretnych skokach (zdarzeniach), a nie w sposób ciągły.
Alternatywa: symulacja krokowa (time-step)
Naiwne podejście — iteruj co sekundę przez każdą osobę:
dla każdej sekundy T od 00:00 do 24:00:
dla każdej osoby P spośród 120 000:
jeśli P.next_event_time == T:
obsłuż zdarzenieKoszt: 86 400 sek × 120 000 osób = ~10 miliardów iteracji dziennie. Ogromna większość z nich to puste "nic się nie zmieniło".
DES: skacz od zdarzenia do zdarzenia
dopóki scheduler nie jest pusty:
pobierz zdarzenie (T, P, A) z najmniejszym T
obsłuż: oblicz duration, next_activity, zapisz log
wstaw do schedulera: (T + duration, P, next_activity)Koszt: tylko tyle iteracji ile jest zdarzeń. Przy ~120 000 osobach i ~20 zdarzeniach dziennie = ~2 400 000 zdarzeń/dzień symulacji. Przy speed=60 (1 min realna = 1 h symulacyjna) demon przetwarza dobę w ~24 sekundy.
2. Główna pętla
┌──────────────────────────────────────────────────┐
│ SCHEDULER (min-heap) │
│ │
│ (T=06:31, id=4821, EVT_WAKEUP) ← najmniejszy │
│ (T=06:33, id=9104, EVT_WAKEUP) │
│ (T=06:34, id= 17, EVT_WAKEUP) │
│ (T=06:35, id=7722, EVT_SLEEP ) │
│ ... │
└───────────────┬──────────────────────────────────┘
│ scheduler_pop()
▼
┌──────────────────────────────────────────────────┐
│ sim_process_event(item) │
│ │
│ 1. activity_unit(akt) → lokal │
│ 2. activity_duration(akt)→ czas_trwania │
│ czas_konca = czas_startu + czas_trwania │
│ 3. next_activity(akt) → nastepna │
│ 4. activity_unit(nastepna)→ nastepny_lokal │
│ 5. elog_write(...) → plik logu │
│ 6. aktualizuj stan osoby │
│ 7. plan_daily_meeting / try_breakup / try_birth │
│ 8. try_work_encounter / try_shop_flirt │
└───────────────┬──────────────────────────────────┘
│ scheduler_push(czas_konca, id, nastepna)
▼
┌──────────────────────────────────────────────────┐
│ SCHEDULER (min-heap) │
│ (T=06:33, id=9104, EVT_WAKEUP) ← nowy min │
│ (T=06:34, id= 17, EVT_WAKEUP) │
│ (T=06:35, id=7722, EVT_SLEEP ) │
│ (T=06:46, id=4821, EVT_BREAKFAST) ← właśnie │
│ ... dodane │
└──────────────────────────────────────────────────┘Łańcuch jest samo-zasilający się: każde zdarzenie natychmiast planuje następne. Żadna osoba nigdy nie "wypadnie" z harmonogramu — dopóki demon działa, każda ma dokładnie 1 oczekujące zdarzenie.
3. Scheduler: min-heap z generacjami
Min-heap
Scheduler to binarna kolejka priorytetowa (min-heap) sortowana po fire_time.
Wstawienie (push): O(log N)
Pobranie min (pop): O(log N)
Peek min: O(1)
Przy N = 120 000 zdarzeń:
log2(120 000) ≈ 17 porównań na operacjęNie ma potrzeby usuwania zdarzeń ze środka kopca — stale event detection (patrz niżej) sprawia, że nieaktualne zdarzenia są odrzucane przy pobraniu.
Problem: unieważnianie zdarzeń
Gdy force_cohabit_sex() lub force_morning_sex() musi natychmiast zmienić harmonogram osoby B, jej stare zdarzenie nadal siedzi gdzieś w kopcu. Usunięcie ze środka kopca to O(N) — za wolne.
Rozwiązanie: licznik generacji (sched_gen)
Każda osoba ma uint8_t sched_gen. Każde zdarzenie nosi gen z chwili wstawienia.
Unieważnienie harmonogramu osoby B:
B.sched_gen++ ← inkrementuj
scheduler_push(nowy_czas, B.id, nowy_akt, B.sched_gen)
Gdy stare zdarzenie B zostanie pobrane z kopca:
if (item.gen != osoba->sched_gen) return; ← odrzuć Kopiec przed unieważnieniem Kopiec po
───────────────────────── ──────────────────────────
min → (T=19:45, B, WATCH_TV, gen=3) (T=19:45, B, WATCH_TV, gen=3) ← zostanie pominięte
(T=20:00, A, SEX_HOME, gen=7) (T=19:45, B, SEX_HOME, gen=4) ← nowe, wygra
(T=20:00, B, SEX_HOME, gen=4) (T=20:00, A, SEX_HOME, gen=7)
... ...Koszt: O(log N) na wstawienie nowego + O(1) odrzucenie starego przy pobraniu. sched_gen to uint8_t — zawija się po 256. Nie stanowi problemu, bo między zawarciem a sprawdzeniem nie może dojść do 256 zmian dla tej samej osoby w jednym ticku.
4. Deterministyczna pseudolosowość
prand(person_id, day_epoch, salt) → uint32_t
// XOR-Shift Hash z mnożnikami Knutha:
uint32_t h = person_id ^ (day_epoch * 2654435761u) ^ ((uint32_t)salt * 40503u);
h ^= h >> 16;
h *= 0x45d9f3b;
h ^= h >> 16;
return h;Trzy właściwości:
┌──────────────┬──────────────────────────────────────────────────────┐
│ Właściwość │ Znaczenie │
├──────────────┼──────────────────────────────────────────────────────┤
│ Bezstanowość │ Brak globalnego stanu → bezpieczne wielowątkowo, │
│ │ wyniki nie zależą od kolejności wywołań │
├──────────────┼──────────────────────────────────────────────────────┤
│ Powtarzalność│ Ta sama (person_id, day_epoch, salt) → zawsze ten │
│ │ sam wynik → symulacja jest w pełni deterministyczna │
│ │ dla danego snapshotu startowego │
├──────────────┼──────────────────────────────────────────────────────┤
│ Niezależność │ Każda odrębna decyzja ma unikatowy salt (0–95+) → │
│ │ brak korelacji między np. godziną wstania (salt=0) │
│ │ a decyzją o małżeństwie (salt=89) │
└──────────────┴──────────────────────────────────────────────────────┘Wspólne decyzje pary: shared_id = min(A.id, B.id)
Gdy para A i B musi podjąć wspólną decyzję (np. o której godzinie się spotkać), oboje wywołują prand(shared_id, day, salt) niezależnie i dostają identyczny wynik:
Osoba A (id=1200) budzi się → plan_daily_meeting():
shared_id = min(1200, 3847) = 1200
meet_time = day + H(19) + prand(1200, day, 44) % H(3)
meet_time = day + 19:00 + 37 min → 19:37
Osoba B (id=3847) budzi się (może minutę później) → plan_daily_meeting():
shared_id = min(1200, 3847) = 1200
meet_time = day + H(19) + prand(1200, day, 44) % H(3)
meet_time = day + 19:00 + 37 min → 19:37 ← identyczny wynik!Brak komunikacji między osobami. Brak synchronizacji. Każda oblicza to samo.
variance(person_id, day, salt, range) → int32_t
Zwraca losową wariację z przedziału [-range, +range]. Używana wszędzie tam, gdzie czas bazowy powinien być "ludzki" (nie do co sekundy):
wakeup_time = H(6) + M(30) + variance(id, day, 0, M(30))
↑ bazowo 06:30 ↑ ±30 min — wynik: 06:00–07:005. Maszyna stanów — harmonogram dnia
Każda osoba podąża ścieżką zdarzeń zależną od swojego statusu.
Pracownik (STATUS_EMPLOYED)
06:30 08:00 12:00 12:45 16:30 18:00 22:30
│ │ │ │ │ │ │
SLEEP ──► WAKEUP ──► BREAKFAST ──► COMMUTE ──► WORK ──► BREAK ──► WORK ──► COMMUTE ──► HOME_REST
▲ TO_WORK (4h±20m) (45m±10m) (4h±20m) FROM_WORK │
│ ┌─────┤
│ DINNER GROCERY
│ │
│ WATCH_TV / HOME_REST
│ │
└──────────────────────────────────────────────────────────── FALLING_ASLEEP ◄─────┘Uczeń (STATUS_STUDENT / STATUS_CHILD)
07:00 07:15 08:00 10:30 10:45 13:00 15:00
│ │ │ │ │ │ │
WAKEUP ──► BREAKFAST ──► COMMUTE ──► SCHOOL ──► BREAK ──► SCHOOL ──► COMMUTE ──► HOME_LEARNING ──► HOME_REST
TO_SCHOOL (2.5h) (15 min) (2.5h) FROM_SCHOOL (2h±30m)Emeryt / bezrobotny (STATUS_RETIRED / UNEMPLOYED)
08:00 08:15 08:45 18:00 19:00 22:30
│ │ │ │ │ │
WAKEUP ──► BREAKFAST ──► HOME_REST ──────────► DINNER ──► WATCH_TV ──► FALLING_ASLEEP ──► SLEEP
(cały dzień)Weekendy — dodatkowe aktywności
Sobota:
┌── 9:00–13:00: GROCERY_SHOPPING (kobiety >18 lat, 70%)
├── 13:00–15:00: LUNCH (pary kohabitujące)
└── 16:00–23:00: SEX_HOME (pary COHABIT, 90%/70% z/bez dzieci)
lub CLUB_NIGHT (single 18–40 lat, 8%)
Niedziela:
├── 10:00–12:00: HOME_LEARNING (uczniowie, 70%)
├── 13:00–15:00: LUNCH (pary kohabitujące)
└── 16:00–23:00: SEX_HOME (pary COHABIT, 80% — tylko jeśli brak sobotniego seksu)Wieczorne wyjścia po kolacji (weekend, salt=75)
rd = prand(id, day, 75) % 100
0–19 │██████████████████████│ WALK (20%, wiek ≥ 7)
20–32 │█████████████│ MEET_FRIENDS (13%, wiek ≥ 18)
33–40 │████████│ VISIT_FAMILY ( 8%, wiek ≥ 7)
41–45 │█████│ RESTAURANT ( 5%, wiek ≥ 18)
46–49 │████│ CINEMA_THEATRE ( 4%, wiek ≥ 12)
50–52 │███│ (tylko sob) HOME_PARTY ( 3%, wiek ≥ 18)
53–99 │ zostajemy w domu6. Synchronizacja par
Dwa modele seksu wymagają koordynacji między osobami:
Model HOST/GUEST (para z osobnych domów)
OSOBA A (HOST, id=1200) OSOBA B (GUEST, id=3847)
──────────────────────── ────────────────────────
18:00 HOME_REST 18:00 HOME_REST
(plan_cap skraca 17:23 HOME_REST kończy się
do 19:37) (cap = meet_time - travel_time)
19:37 WAIT_FOR_PARTNER ◄───────19:23 TRAVEL_TO_PARTNER (14 min)
19:37 SEX_HOST ◄───────19:37 SEX_GUEST
21:10 HOME_REST 21:10 STAY_OVERNIGHT / MORNING_RETURNOboje obliczają meet_time = 19:37 niezależnie (shared_id = 1200). Gość wychodzi 14 minut wcześniej (trigger = meet_time - travel_time).
Model COHABIT (para we wspólnym domu)
Inicjator A wchodzi w EVT_SEX_HOME. Partner B może być jeszcze w WATCH_TV:
OSOBA A (PLAN_COHABIT) OSOBA B (nie dobił do meet_time)
──────────────────────── ────────────────────────
19:37 SEX_HOME ─────────────────► force_cohabit_sex() wywołane
(sim_process_event) B.sched_gen++
elog_write(SEX_HOME, B)
B.current_activity = SEX_HOME
scheduler_push(21:10, B, HOME_REST, gen=4)
21:10 HOME_REST 21:10 HOME_RESTStare zdarzenie B (WATCH_TV, gen=3) zostanie odrzucone gdy osiągnie czoło kolejki.
Poranny seks (MORNING_SEX)
~06:45 next_activity(SLEEP, A) = MORNING_SEX ← decyzja A (15%, salt=77)
force_morning_sex(sched, B, czas_konca)
B.sched_gen++
scheduler_push(06:45, B, MORNING_SEX, gen=new)
06:45 A: EVT_MORNING_SEX 06:45 B: EVT_MORNING_SEX
(A normalnie procesuje) (B procesuje swoje zdarzenie)
06:50 A: EVT_WAKEUP 06:50 B: EVT_WAKEUPB nie wie, że A zdecydowało. Scheduler robi całą robotę.
7. Wydajność
Złożoność obliczeniowa
┌─────────────────────────────┬──────────────┬───────────────────────────┐
│ Operacja │ Złożoność │ Uwaga │
├─────────────────────────────┼──────────────┼───────────────────────────┤
│ scheduler_push / pop │ O(log N) │ N = liczba osób ≈ 120 000 │
│ city_person(id) │ O(1) │ tablica lookup pers_by_id │
│ city_unit(id) │ O(1) │ tablica lookup unit_by_id │
│ city_org(id) │ O(1) │ tablica lookup org_by_id │
│ prand() │ O(1) │ ~6 operacji CPU │
│ travel_time(from, to) │ O(1) │ lookup + arytmetyka │
│ QUERY_STATS (IPC) │ O(1) │ act_count pre-wyliczone │
│ LIST_ACTIVITY (IPC) │ O(N) │ skan wszystkich osób │
└─────────────────────────────┴──────────────┴───────────────────────────┘Zużycie pamięci
person_record_t = 84 bajty × 120 000 osób ≈ 10 MB
daily_plan_t = ~32 bajty × 120 000 ≈ 4 MB
sat_had_sex[] = 1 bajt × 120 000 ≈ 120 KB
act_count[][] = 1024 × 2 × 4 bajty ≈ 8 KB
scheduler heap = ~16 bajty × 120 000 ≈ 2 MB
lookup arrays = 4 bajty × max_id × 4 ≈ 2 MB
─────────────────────────────────────────────────────
Razem (struktury danych) ≈ 18 MBBez alokacji pamięci w gorącej ścieżce (sim_process_event): żadnego malloc, calloc ani free w pętli głównej.
Przepustowość
120 000 osób × 20 zdarzeń/osobę/dobę = 2 400 000 zdarzeń/dobę
Przy speed=60 (1 min realna = 1 h symulacyjna):
1 doba symulacyjna = 24 minuty realne
2 400 000 ÷ (24 × 60) ≈ 1 667 zdarzeń/sekundę realną
Przy speed=3600 (catchup, pełna prędkość CPU):
~2–5 milionów zdarzeń/sekundę (zależy od sprzętu)
1 doba symulacyjna w ciągu ~1 sekundyBrak alokacji w hot path
// sim_process_event() — zero malloc, zero I/O (oprócz buforowanego logu):
void sim_process_event(city_t *miasto, scheduler_t *sched,
event_log_t *elog, const sched_item_t *item,
FILE *console)
{
person_record_t *osoba = city_person(miasto, item->person_id); // O(1) lookup
// ... wszystkie zmienne na stosie, żadnych heap allocations
scheduler_push(sched, czas_konca, osoba->id, nastepna, osoba->sched_gen);
}Log zdarzeń
Bufor stdio: 256 KB (unikamy syscalli write() co zdarzenie)
Format: pipe-separated, ~80 bajtów/linia
Przy 2.4M zdarzeń/dobę: ~192 MB/dobę logu
Logrotate: codzienna rotacja z SIGHUP (reopen bez restartu demona)8. Skalowanie: miasto 2M i państwo 40M mieszkańców
Jak zmienia się obciążenie
┌──────────────────────┬─────────────┬─────────────┬──────────────┐
│ Metryka │ 120 000 │ 2 000 000 │ 40 000 000 │
│ │ (Gorzów) │ (Warszawa) │ (Polska) │
├──────────────────────┼─────────────┼─────────────┼──────────────┤
│ Zdarzeń/dobę │ 2.4 M │ 40 M │ 800 M │
│ log2(N) scheduler │ 17 │ 21 │ 25 │
│ RAM — persons │ 10 MB │ 168 MB │ 3.4 GB │
│ RAM — razem │ 18 MB │ 300 MB │ 6.0 GB │
│ Czas doby (catchup) │ ~1 s │ ~10 s │ ~3 min │
│ Log/dobę │ 190 MB │ 3.2 GB │ 64 GB │
└──────────────────────┴─────────────┴─────────────┴──────────────┘Kluczowa obserwacja: złożoność rośnie liniowo z N, nie kwadratowo. Każda osoba generuje stałą liczbę zdarzeń (~20/dobę) niezależnie od rozmiarów populacji. Operacje na schedulerze rosną tylko logarytmicznie (log2(40M) ≈ 25, log2(120K) ≈ 17 — różnica zaledwie 8 porównań na operację).
Ilość zdarzeń będzie oczywiście rosnąć w przypadku implementacji dodatkowych aktywności, np. symulacji przestępczości. Nadal jednak architektura rozwiązania pozwala na symulację nawet całej Polski na dość podstawowym serwerze dedykowanym.
Wyzwanie 1: presja pamięci i cache miss
Przy 40M osobach tablica persons[] zajmuje ~3.4 GB — nie mieści się w L3 cache (typowe serwery: 16–64 MB L3). Każdy losowy dostęp city_person(id) to potencjalny cache miss (~100 ns kara zamiast ~1 ns z cache).
Przy 120K: persons[] = 10 MB → mieści się w L3 (ciepły cache)
Przy 2M: persons[] = 168 MB → część w RAM, cache miss ~5–20% dostępów
Przy 40M: persons[] = 3.4 GB → niemal każdy dostęp to RAM hit, ~100 ns kara
Skutek dla 40M:
800M zdarzeń/dobę × 2 dostępy × 100 ns = ~160 sekund samych cache miss
→ catchup ~3 minuty zamiast ~1 sekundy dla 120KRemedium bez zmiany architektury: partycjonowanie geograficzne. Osoby z tej samej dzielnicy mają zbliżone id → lokalność odwołań rośnie naturalnie jeśli generator przydziela id sekwencyjnie per dzielnica.
Wyzwanie 2: rozmiar logu
40M × 20 zdarzeń × 80 bajtów = 64 GB/dobę
Opcje:
a) Selektywny log: logować tylko zdarzenia relacyjne (EVT_FIRST_MEETING,
EVT_WEDDING, EVT_BIRTH...) → redukuje log 50× do ~1.3 GB/dobę
b) Format binarny zamiast pipe-separated → redukuje 3× do ~20 GB/dobę
c) Próbkowanie: logować 1% osób pełnie, resztę tylko zdarzenia kluczowe
d) Strumieniowanie przez socket zamiast zapisu na dysk (konsument przetwarza
zdarzenia na bieżąco bez trwałego składowania)Wyzwanie 3: interakcje społeczne
Funkcje try_work_encounter() i try_shop_flirt() szukają kandydata spośród pracowników tej samej organizacji (do 10 prób). Przy 40M osobach organizacje mogą liczyć tysiące pracowników:
Obecna implementacja: do 10 prób → O(1) per zdarzenie, O(N) łącznie
Przy 40M: nadal O(1) per zdarzenie — żadna skrzynka nie rośnieJednak gęstość interakcji rośnie: w dużej org (np. 5000 pracowników) losowy kandydat z 10 prób prawie zawsze jest w WORK_BREAK → wskaźnik rozmów wzrośnie nieproporcjonalnie. Remedium: limit org (max ~200 pracowników dla jednej lokalizacji) lub przeskalowanie prawdopodobieństwa 30% przez 1/sqrt(org_size).
Wyzwanie 4: typy danych — uint32_t
Obecne person_id, unit_id, org_id to uint32_t (max ~4.3 miliarda). Dla 40M nie wymaga żadnych zmian. Jedyna potencjalna granica to max_pers_id używany do alokacji tablic lookup — przy 40M oznacza to ~160 MB samych wskaźników.
Dlaczego architektura jest wystarczająca
Trzy właściwości projektowe sprawiają, że obecna architektura skaluje się bez przepisywania od zera:
1. Brak globalnych blokad i współdzielonego stanu między osobami.
Każda osoba jest niezależnym agentem. Jedyny współdzielony stan to:
scheduler(jeden, ale wielowątkowy min-heap jest trywialny do implementacji)act_count[][](kilka atomowych inkrementów/dekrementów)- tablice
plans[],sat_had_sex[](person-indexed, brak konfliktów)
Obecna architektura → wielowątkowość przez partycjonowanie populacji:
Wątek 1: osoby id 1 – 10 000 000
Wątek 2: osoby id 10 000 001 – 20 000 000
Wątek 3: osoby id 20 000 001 – 30 000 000
Wątek 4: osoby id 30 000 001 – 40 000 000
Synchronizacja potrzebna tylko gdy:
- force_cohabit_sex(partner) → partner w innej partycji (rzadkie, ~1% par)
- try_work_encounter(target) → target w innej partycji (rzadkie)
→ trylock + queue per wątek eliminuje contention2. Algorytm jest lokalny — osoba decyduje tylko na podstawie swoich danych.
prand() nie wymaga komunikacji z innymi osobami. plan_daily_meeting() oblicza identyczny wynik niezależnie po obu stronach pary. Brak "głosowania", brak barier synchronizacji.
3. Złożoność czasowa jest O(N log N) per dobę, nie O(N²).
Najczęstsze operacje (push/pop schedulera) to O(log N). Interakcje społeczne są O(1) per osoba. Brak globalnego skanu populacji w hot path (poza LIST_ACTIVITY które jest operacją diagnostyczną, nie symulacyjną).
Dlaczego symulacja będzie wiarygodna przy większej skali
Agent-based modeling — każda osoba jest niezależnym agentem z własnym stanem — jest uznaną metodą w demografii i socjologii obliczeniowej. Kluczowe właściwości zapewniające wiarygodność:
Emergentna statystyka z deterministycznych reguł. Żadna reguła w kodzie nie mówi "20% małżeństw rozpada się do 10 lat". To wynika z indywidualnych reguł (staz ≥ 7 lat → 0.05%/dzień → po 7 latach prawdopodobieństwo ~13% rocznie), które przy milionach par dają rozkłady zgodne z danymi GUS — bez kalibracji ad-hoc.
Heterogeniczność populacji. Każda z 40 milionów osób ma inny wiek, status, wykształcenie, historię związków. Agregowane modele (np. równania różniczkowe) nie uchwycą ogona rozkładu — nastolatka ze statusem CHILD i emeryt ze statusem RETIRED zachowują się kompletnie inaczej, co jest odzwierciedlone w kodzie dosłownie.
Wariancja per-osoba, nie per-populacja. variance(id, day, salt, range) sprawia, że dwie identyczne statystycznie osoby jednak różnią się w konkretnych decyzjach każdego dnia. Populacja 40M generuje naturalne rozkłady Gaussa tam gdzie są oczekiwane (godziny wstania) i rozkłady potęgowe tam gdzie modele socjologiczne ich przewidują (czas trwania związków).
Powtarzalność = falsyfikowalność. Ta sama populacja startowa (snapshot) zawsze daje identyczną historię. To pozwala na naukowe testowanie hipotez: "co by się stało, gdyby szansa na romans wzrosła z 5% do 10%?" — zmień jeden parametr, uruchom dwie instancje z tym samym seedem, porównaj logi.
Snapshot A (seed=42) + reguła oryginalna → wyniki_A.log
Snapshot A (seed=42) + zmodyfikowana reguła → wyniki_B.log
diff wyniki_A.log wyniki_B.log
→ dokładnie te osoby i te zdarzenia które zmieniła nowa regułaTopologia przestrzenna. Czas dojazdu travel_time() oparty na rzeczywistej geometrii miasta sprawia, że osoby z odległych dzielnic rzadziej się spotykają — co jest zgodne z badaniami socjologicznymi nad geografią sieci społecznych. Przy skalowaniu do 40M (cały kraj) topologia deterministycznie wymusza regionalne klastrowanie relacji.