Re: x264 benchmarks BFS vs CFS

[Jason Garrett-Glaser <darkshikari@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 3234 bytes --]

On Thu, Dec 17, 2009 at 11:30 PM, Mike Galbraith <efault@gmx.de> wrote:
> On Fri, 2009-12-18 at 06:23 +0100, Ingo Molnar wrote:
>
>> Having said that, we generally try to make things perform well without apps
>> having to switch themselves to SCHED_BATCH. Mike, do you think we can make
>> x264 perform as well (or nearly as well) under SCHED_OTHER as under
>> SCHED_BATCH?
>
> It's not bad as is, except for ultrafast mode.  START_DEBIT is the
> biggest problem there.  I don't think SCHED_OTHER will ever match
> SCHED_BATCH for this load, though I must say I haven't full-spectrum
> tested.  This load really wants RR scheduling, and wakeup preemption
> necessarily perturbs run order.
>
> I'll probably piddle with it some more, it's an interesting load.
>
>        -Mike
>
>

Two more thoughts here:

1) We're considering moving to a thread pool soon; we already have a
working patch for it and if anything it'll save a few clocks spent on
nice()ing threads and other such things.  Will this improve
START_DEBIT at all?  I've attached the beta patch if you want to try
it.  Note this also works with 2) as well, so it adds yet another
dimension to what's mentioned below.

2) We recently implemented a new threading model which may be
interesting to test as well.  This threading model gives worse
compression *and* performance, but has one benefit: it adds zero
latency, whereas normal threading adds a full frame of latency per
thread.  This was paid for by a company interested in
ultra-low-latency streaming applications, where 1 millisecond is a
huge deal.  I've been thinking this might be interesting to bench from
a kernel perspective as well, as when you're spawning a half-dozen
threads and need them all done within 6 milliseconds, you start
getting down to serious scheduler issues.

The new threading model is much less complex than the regular one and
works as follows.  The frame is split into X slices, and each slice
encoded with one thread.  Specifically, it works via the following
process:

1.  Preprocess input frame, perform lookahead analysis on input frame
(all singlethreaded)
2.  Split up a ton of threads to do the main encode, one per slice.
3.  Join all the threads.
4.  Do post-filtering on the output frame, return.

Clearly this is an utter disaster, since it spawns N times as many
threads as the old threading model *and* they last far shorter, *and*
only part of the application is multithreaded.  But there's not really
a better way to do low-latency threading, and it's an interesting
challenge to boot.  IIRC, it's also the way ffmpeg's encoder threading
works.  It's widely considered an inferior model, but as mentioned
before, in this particular use-case there's no choice.

To enable this, use --sliced-threads.  I'd recommend using a
higher-resolution clip for this, as it performs atrociously bad on
very low resolution videos for reasons you might be able to guess.  If
you need a higher-res clip, check the SD or HD ones here:
http://media.xiph.org/video/derf/ .

I'm personally curious as to what kind of scheduler issues this
results in--I haven't done any BFS vs CFS tests with this option
enabled yet.

Jason

[-- Attachment #2: thread_pool_slices.diff --]
[-- Type: application/octet-stream, Size: 13295 bytes --]

diff --git a/common/common.h b/common/common.h
index 417ac9e..28d6c1d 100644
--- a/common/common.h
+++ b/common/common.h
@@ -337,12 +337,20 @@ struct x264_t
     /* encoder parameters */
     x264_param_t    param;
 
-    x264_t          *thread[X264_THREAD_MAX+1];
-    x264_pthread_t  thread_handle;
-    int             b_thread_active;
-    int             i_thread_phase; /* which thread to use for the next frame */
-    int             i_threadslice_start; /* first row in this thread slice */
-    int             i_threadslice_end; /* row after the end of this thread slice */
+    x264_t               *thread[X264_THREAD_MAX+1]; /* contexts for each frame in progress + lookahead */
+    x264_pthread_t       *thread_handle;
+    x264_pthread_cond_t  thread_queue_cv;
+    x264_pthread_mutex_t thread_queue_mutex;
+    x264_t               **thread_queue; /* frames that have been prepared but not yet claimed by a worker thread */
+    x264_pthread_cond_t  thread_active_cv;
+    x264_pthread_mutex_t thread_active_mutex;
+    int                  thread_active;
+    int                  b_thread_active;
+    int                  i_thread_phase; /* which thread to use for the next frame */
+    int                  thread_exit;
+    int                  thread_error;
+    int                  i_threadslice_start; /* first row in this thread slice */
+    int                  i_threadslice_end; /* row after the end of this thread slice */
 
     /* bitstream output */
     struct
diff --git a/encoder/encoder.c b/encoder/encoder.c
index 0c0010f..bc0e75b 100644
--- a/encoder/encoder.c
+++ b/encoder/encoder.c
@@ -47,6 +47,53 @@ static int x264_encoder_frame_end( x264_t *h, x264_t *thread_current,
                                    x264_nal_t **pp_nal, int *pi_nal,
                                    x264_picture_t *pic_out );
 
+/* threading */
+
+static void *x264_slices_write_thread( x264_t *h );
+
+#ifdef HAVE_PTHREAD
+static void x264_int_cond_broadcast( x264_pthread_cond_t *cv, x264_pthread_mutex_t *mutex, int *var, int val )
+{
+    x264_pthread_mutex_lock( mutex );
+    *var = val;
+    x264_pthread_cond_broadcast( cv );
+    x264_pthread_mutex_unlock( mutex );
+}
+
+static void x264_int_cond_wait( x264_pthread_cond_t *cv, x264_pthread_mutex_t *mutex, int *var, int val )
+{
+    x264_pthread_mutex_lock( mutex );
+    while( *var != val )
+        x264_pthread_cond_wait( cv, mutex );
+    x264_pthread_mutex_unlock( mutex );
+}
+
+#else
+static void x264_int_cond_broadcast( x264_pthread_cond_t *cv, x264_pthread_mutex_t *mutex, int *var, int val )
+{}
+static void x264_int_cond_wait( x264_pthread_cond_t *cv, x264_pthread_mutex_t *mutex, int *var, int val )
+{}
+#endif
+
+static void x264_thread_pool_push( x264_t *h )
+{
+    assert( h->thread_active == 0 );
+    h->thread_active = 1;
+    assert( h->b_thread_active == 0 );
+    h->b_thread_active = 1;
+    x264_pthread_mutex_lock( &h->thread[0]->thread_queue_mutex );
+    x264_frame_push( (void*)h->thread_queue, (void*)h );
+    x264_pthread_cond_broadcast( &h->thread[0]->thread_queue_cv );
+    x264_pthread_mutex_unlock( &h->thread[0]->thread_queue_mutex );
+}
+
+static int x264_thread_pool_wait( x264_t *h )
+{
+    x264_int_cond_wait( &h->thread_active_cv, &h->thread_active_mutex, &h->thread_active, 0 );
+    h->b_thread_active = 0;
+    return h->thread_error;
+}
+
 /****************************************************************************
  *
  ******************************* x264 libs **********************************
@@ -943,6 +990,16 @@ x264_t *x264_encoder_open( x264_param_t *param )
     for( i = 1; i < h->param.i_threads + !!h->param.i_sync_lookahead; i++ )
         CHECKED_MALLOC( h->thread[i], sizeof(x264_t) );
 
+    if( h->param.i_threads > 1 )
+    {
+        CHECKED_MALLOCZERO( h->thread_handle, (h->param.i_threads + 1) * sizeof(x264_pthread_t) );
+        CHECKED_MALLOCZERO( h->thread_queue, (h->param.i_threads + 1) * sizeof(x264_t*) );
+        if( x264_pthread_cond_init( &h->thread_queue_cv, NULL ) )
+            goto fail;
+        if( x264_pthread_mutex_init( &h->thread_queue_mutex, NULL ) )
+            goto fail;
+    }
+
     if( x264_lookahead_init( h, i_slicetype_length ) )
         goto fail;
 
@@ -967,6 +1024,14 @@ x264_t *x264_encoder_open( x264_param_t *param )
         CHECKED_MALLOC( h->thread[i]->out.nal, init_nal_count*sizeof(x264_nal_t) );
         h->thread[i]->out.i_nals_allocated = init_nal_count;
 
+        if( h->param.i_threads > 1 )
+        {
+            if( x264_pthread_cond_init( &h->thread[i]->thread_active_cv, NULL ) )
+                goto fail;
+            if( x264_pthread_mutex_init( &h->thread[i]->thread_active_mutex, NULL ) )
+                goto fail;
+        }
+
         if( allocate_threadlocal_data && x264_macroblock_cache_init( h->thread[i] ) < 0 )
             goto fail;
     }
@@ -1009,6 +1074,13 @@ x264_t *x264_encoder_open( x264_param_t *param )
         h->sps->i_profile_idc == PROFILE_HIGH ? "High" :
         "High 4:4:4 Predictive", h->sps->i_level_idc/10, h->sps->i_level_idc%10 );
 
+    if( h->param.i_threads > 1 )
+    {
+        for( i = 0; i < h->param.i_threads; i++ )
+            if( x264_pthread_create( &h->thread_handle[i], NULL, (void*)x264_slices_write_thread, h ) )
+                return NULL;
+    }
+
     return h;
 fail:
     x264_free( h );
@@ -1723,7 +1795,7 @@ static int x264_slice_write( x264_t *h )
             h->mb.b_reencode_mb = 0;
 
 #if VISUALIZE
-        if( h->param.b_visualize )
+        if( h->i_threads == 1 && h->param.b_visualize )
             x264_visualize_mb( h );
 #endif
 
@@ -1851,24 +1923,10 @@ static void x264_thread_sync_stat( x264_t *dst, x264_t *src )
     memcpy( &dst->stat.i_frame_count, &src->stat.i_frame_count, sizeof(dst->stat) - sizeof(dst->stat.frame) );
 }
 
-static void *x264_slices_write( x264_t *h )
+static int x264_slices_write_internal( x264_t *h )
 {
     int i_slice_num = 0;
     int last_thread_mb = h->sh.i_last_mb;
-    if( h->param.i_sync_lookahead )
-        x264_lower_thread_priority( 10 );
-
-#ifdef HAVE_MMX
-    /* Misalign mask has to be set separately for each thread. */
-    if( h->param.cpu&X264_CPU_SSE_MISALIGN )
-        x264_cpu_mask_misalign_sse();
-#endif
-
-#if VISUALIZE
-    if( h->param.b_visualize )
-        if( x264_visualize_init( h ) )
-            return (void *)-1;
-#endif
 
     /* init stats */
     memset( &h->stat.frame, 0, sizeof(h->stat.frame) );
@@ -1887,10 +1945,30 @@ static void *x264_slices_write( x264_t *h )
         }
         h->sh.i_last_mb = X264_MIN( h->sh.i_last_mb, last_thread_mb );
         if( x264_stack_align( x264_slice_write, h ) )
-            return (void *)-1;
+            return -1;
         h->sh.i_first_mb = h->sh.i_last_mb + 1;
     }
 
+    return 0;
+}
+
+static int x264_slices_write( x264_t *h )
+{
+#ifdef HAVE_MMX
+    /* Misalign mask has to be set separately for each thread. */
+    if( h->param.cpu&X264_CPU_SSE_MISALIGN )
+        x264_cpu_mask_misalign_sse();
+#endif
+
+#if VISUALIZE
+    if( h->param.b_visualize )
+        if( x264_visualize_init( h ) )
+            return -1;
+#endif
+
+    if( x264_slices_write_internal( h ) )
+        return -1;
+
 #if VISUALIZE
     if( h->param.b_visualize )
     {
@@ -1899,13 +1977,47 @@ static void *x264_slices_write( x264_t *h )
     }
 #endif
 
+    return 0;
+}
+
+static void *x264_slices_write_thread( x264_t *h )
+{
+    if( h->param.i_sync_lookahead )
+        x264_lower_thread_priority( 10 );
+
+#ifdef HAVE_MMX
+    /* Misalign mask has to be set separately for each thread. */
+    if( h->param.cpu&X264_CPU_SSE_MISALIGN )
+        x264_cpu_mask_misalign_sse();
+#endif
+
+    for(;;)
+    {
+        x264_t *t = NULL;
+
+        // get one frame from the queue
+        x264_pthread_mutex_lock( &h->thread_queue_mutex );
+        while( !h->thread_queue[0] && !h->thread_exit )
+            x264_pthread_cond_wait( &h->thread_queue_cv, &h->thread_queue_mutex );
+        if( h->thread_queue[0] )
+            t = (void*)x264_frame_shift( (void*)h->thread_queue );
+        x264_pthread_mutex_unlock( &h->thread_queue_mutex );
+        if( h->thread_exit )
+            return (void *)0;
+        if( !t )
+            continue;
+
+        t->thread_error = x264_slices_write_internal( t );
+
+        x264_int_cond_broadcast( &t->thread_active_cv, &t->thread_active_mutex, &t->thread_active, 0 );
+    }
+
     return (void *)0;
 }
 
 static int x264_threaded_slices_write( x264_t *h )
 {
     int i, j;
-    void *ret = NULL;
     /* set first/last mb and sync contexts */
     for( i = 0; i < h->param.i_threads; i++ )
     {
@@ -1928,14 +2040,10 @@ static int x264_threaded_slices_write( x264_t *h )
 
     /* dispatch */
     for( i = 0; i < h->param.i_threads; i++ )
-        if( x264_pthread_create( &h->thread[i]->thread_handle, NULL, (void*)x264_slices_write, (void*)h->thread[i] ) )
-            return -1;
+        x264_thread_pool_push( h->thread[i] );
     for( i = 0; i < h->param.i_threads; i++ )
-    {
-        x264_pthread_join( h->thread[i]->thread_handle, &ret );
-        if( (intptr_t)ret )
-            return (intptr_t)ret;
-    }
+        if( x264_thread_pool_wait( h->thread[i] ) )
+            return -1;
 
     /* deblocking and hpel filtering */
     for( i = 0; i <= h->sps->i_mb_height; i++ )
@@ -2238,18 +2346,14 @@ int     x264_encoder_encode( x264_t *h,
     h->i_threadslice_start = 0;
     h->i_threadslice_end = h->sps->i_mb_height;
     if( !h->param.b_sliced_threads && h->param.i_threads > 1 )
-    {
-        if( x264_pthread_create( &h->thread_handle, NULL, (void*)x264_slices_write, h ) )
-            return -1;
-        h->b_thread_active = 1;
-    }
+        x264_thread_pool_push( h );
     else if( h->param.b_sliced_threads )
     {
         if( x264_threaded_slices_write( h ) )
             return -1;
     }
     else
-        if( (intptr_t)x264_slices_write( h ) )
+        if( x264_slices_write( h ) )
             return -1;
 
     return x264_encoder_frame_end( thread_oldest, thread_current, pp_nal, pi_nal, pic_out );
@@ -2263,13 +2367,8 @@ static int x264_encoder_frame_end( x264_t *h, x264_t *thread_current,
     char psz_message[80];
 
     if( h->b_thread_active )
-    {
-        void *ret = NULL;
-        x264_pthread_join( h->thread_handle, &ret );
-        if( (intptr_t)ret )
-            return (intptr_t)ret;
-        h->b_thread_active = 0;
-    }
+        if( x264_thread_pool_wait( h ) )
+            return -1;
     if( !h->out.i_nal )
     {
         pic_out->i_type = X264_TYPE_AUTO;
@@ -2472,15 +2571,29 @@ void    x264_encoder_close  ( x264_t *h )
 
     x264_lookahead_delete( h );
 
-    for( i = 0; i < h->param.i_threads; i++ )
+    if( h->param.i_threads > 1 )
     {
         // don't strictly have to wait for the other threads, but it's simpler than canceling them
-        if( h->thread[i]->b_thread_active )
+        x264_pthread_mutex_lock( &h->thread_queue_mutex );
+        h->thread_exit = 1;
+        x264_pthread_cond_broadcast( &h->thread_queue_cv );
+        x264_pthread_mutex_unlock( &h->thread_queue_mutex );
+        for( i = 0; i < h->param.i_threads; i++ )
+            x264_pthread_join( h->thread_handle[i], NULL );
+        for( i = 0; i < h->param.i_threads; i++ )
         {
-            x264_pthread_join( h->thread[i]->thread_handle, NULL );
-            assert( h->thread[i]->fenc->i_reference_count == 1 );
-            x264_frame_delete( h->thread[i]->fenc );
+            x264_pthread_cond_destroy( &h->thread[i]->thread_active_cv );
+            x264_pthread_mutex_destroy( &h->thread[i]->thread_active_mutex );
+            if( h->thread[i]->b_thread_active )
+            {
+                assert( h->thread[i]->fenc->i_reference_count == 1 );
+                x264_frame_delete( h->thread[i]->fenc );
+            }
         }
+        x264_pthread_cond_destroy( &h->thread_queue_cv );
+        x264_pthread_mutex_destroy( &h->thread_queue_mutex );
+        x264_free( h->thread_handle );
+        x264_free( h->thread_queue );
     }
 
     if( h->param.i_threads > 1 && !h->param.b_sliced_threads )
diff --git a/encoder/lookahead.c b/encoder/lookahead.c
index f33b167..039b9cb 100644
--- a/encoder/lookahead.c
+++ b/encoder/lookahead.c
@@ -152,7 +152,7 @@ int x264_lookahead_init( x264_t *h, int i_slicetype_length )
     if( x264_macroblock_cache_init( look_h ) )
         goto fail;
 
-    if( x264_pthread_create( &look_h->thread_handle, NULL, (void *)x264_lookahead_thread, look_h ) )
+    if( x264_pthread_create( &h->thread_handle[h->param.i_threads], NULL, (void *)x264_lookahead_thread, look_h ) )
         goto fail;
     look->b_thread_active = 1;
 
@@ -170,7 +170,7 @@ void x264_lookahead_delete( x264_t *h )
         h->lookahead->b_exit_thread = 1;
         x264_pthread_cond_broadcast( &h->lookahead->ifbuf.cv_fill );
         x264_pthread_mutex_unlock( &h->lookahead->ifbuf.mutex );
-        x264_pthread_join( h->thread[h->param.i_threads]->thread_handle, NULL );
+        x264_pthread_join( h->thread_handle[h->param.i_threads], NULL );
         x264_macroblock_cache_end( h->thread[h->param.i_threads] );
         x264_free( h->thread[h->param.i_threads]->scratch_buffer );
         x264_free( h->thread[h->param.i_threads] );