Use merge sort for average frame calc

1 files changed, 65 insertions, 18 deletions

diff --git a/runtime.c b/runtime.c
index 5444139..06cc828 100644
--- a/runtime.c
+++ b/runtime.c
@@ -46,7 +46,7 @@
 //  - Work in progress
 //    - Graphics perf - request cache
 //      Requires:
-//      + [ ] Graphics tests
+//      + [x] Graphics tests
 //      + [x] Graphics requests
 //      + [x] Memory buffer allocator
 //      + [x] Blake2 hash
@@ -56,10 +56,8 @@
 //    - Examples
 //      - Conway's Game of Life
 //      - Julia Set
-//      - Labyrinth
 //      - Chat
 //    - Graphics
-//      - Gamma correction
 //      - Custom fonts - integrate stb_truetype.h
 //      - UI
 //      - Icons
@@ -67,9 +65,6 @@
 //    - Clipboard
 //      - Images - BMP, PPM
 //      - Sound - WAV
-//    - Clipboard
-//      - Images - BMP, PPM
-//      - Sound - WAV
 //    - Dynamic libraries - load dependencies conditionally
 //      - X11
 //      - Wayland
@@ -151,6 +146,7 @@
 //    - Alpha blending
 //    - Self-contained impl
 //    - Anti-aliasing
+//    - Gamma correction
 //  - System
 //    - Dynamic libraries
 //    - Window - X11, Web
@@ -668,7 +664,8 @@ typedef struct {
   b8 key_down    [MAX_NUM_KEYS];
   b8 key_pressed [MAX_NUM_KEYS];
 
-  u64 native_window_handle;
+  void *window_handle_win32;
+  u64   window_handle_x11;
 
   i64 memory_buffer_size;
   u8 *memory_buffer;
@@ -1758,6 +1755,61 @@ void run_main_window_event_loop(void) {
 static i64 _frame_index                         = 0;
 static i64 _frame_duration[NUM_FRAMES_AVERAGED] = {0};
 
+static void merge_sort_i64_(i64 len, i64 *values, i64 *buffer) {
+  if (len <= 0)
+    return;
+
+  if (values == NULL || buffer == NULL) {
+    LOG_error("Sanity");
+    return;
+  }
+
+  i64 *a = values;
+  i64 *b = buffer;
+
+  i64 chunk_size = 1;
+
+  for (; chunk_size < len; chunk_size <<= 1) {
+    for (i64 offset = 0; offset < len; offset += chunk_size * 2) {
+      i64 *s0     = a + offset;
+      i64 *s0_end = s0 + chunk_size;
+      if (s0_end > a + len)
+        s0_end = a + len;
+
+      i64 *s1     = s0_end;
+      i64 *s1_end = s1 + chunk_size;
+      i64 *d      = b + offset;
+      i64 *d_end  = b + chunk_size * 2;
+      if (s1_end > a + len)
+        s1_end = a + len;
+      if (d_end > b + len)
+        d_end = b + len;
+
+      for (; d < d_end; ++d)
+        if (s0 >= s0_end) {
+          *d = *s1;
+          ++s1;
+        } else if (s1 >= s1_end) {
+          *d = *s0;
+          ++s0;
+        } else if (*s0 > *s1) {
+          *d = *s0;
+          ++s0;
+        } else {
+          *d = *s1;
+          ++s1;
+        }
+    }
+
+    i64 *c = a;
+    a = b;
+    b = c;
+  }
+
+  if (a != values)
+    mem_cpy_(values, a, len * sizeof *values);
+}
+
 static i64 average_frame_duration_(i64 duration) {
   _frame_duration[_frame_index] = duration;
   _frame_index = (_frame_index + 1) % NUM_FRAMES_AVERAGED;
@@ -1766,14 +1818,8 @@ static i64 average_frame_duration_(i64 duration) {
   for (i64 i = 0; i < NUM_FRAMES_AVERAGED; ++i)
     durs[i] = _frame_duration[i];
 
-  //  FIXME, PERF: Use better sorting algorithm, e.g. merge sort.
-  for (i64 i = 0; i < (i64) NUM_FRAMES_AVERAGED; ++i)
-    for (i64 j = i + 1; j < NUM_FRAMES_AVERAGED; ++j)
-      if (durs[i] < durs[j]) {
-        i64 t   = durs[i];
-        durs[i] = durs[j];
-        durs[j] = t;
-      }
+  i64 buf[NUM_FRAMES_AVERAGED + 1];
+  merge_sort_i64_(NUM_FRAMES_AVERAGED, durs, buf);
 
   if (AVERAGE_FRAME_BIAS < 0.0 || AVERAGE_FRAME_BIAS > 1.0)
     return durs[0];
@@ -3592,7 +3638,7 @@ void init_main_window(void) {
     return;
   }
 
-  g_platform.native_window_handle = (u64) _window;
+  g_platform.window_handle_x11 = _window;
 
   _im = XOpenIM(_display, NULL, NULL, NULL);
 
@@ -3663,8 +3709,9 @@ void init_main_window(void) {
 void shutdown_all_systems(void) {
   PROFILER_report_();
 
-  g_platform.done                 = 1;
-  g_platform.native_window_handle = 0;
+  g_platform.done = 1;
+
+  g_platform.window_handle_x11 = 0;
 
   if (!g_platform.graceful_shutdown)
     return;