This is an automated email from the git hooks/post-receive script. Git pushed a commit to branch master in repository ffmpeg.
commit c9a6817e3d265c27810e9d8f42da42f6b3196365 Author: Lynne <[email protected]> AuthorDate: Sun Sep 20 20:59:47 2026 +0900 Commit: Lynne <[email protected]> CommitDate: Thu Sep 24 08:03:43 2026 +0900 ffv1enc_vulkan: replace the float32 bitonic sort with a radix sort The bitonic sort needed a 64 KiB shared buffer, more than some devices have, and for larger slices sorted in place in an unqualified buffer with a memoryBarrierBuffer() after the barrier, which under the Vulkan memory model does not make the writes visible to other invocations. It also takes log2(N)^2/2 barriers, 91 for the UHD slices, and a slice of millions of pixels times out the GPU. Replace it with an LSD radix sort, 4 bits per pass, between the pairs region of a plane and a scratch region. Each subgroup owns a block of rows of elements, one per lane, and ranks them with ballots from the digit counts of the blocks, which take up to 16 KiB of shared memory. The bitmaps of the planes now follow the pairs of all planes, as the setup shader only fills them once the sort is done, so their region serves as the scratch and the buffer keeps its size. At UHD with the default slicing on an RX 6900 XT, the sort of a frame goes from 14 ms to 3.4 ms. --- libavcodec/ffv1enc_vulkan.c | 5 +- libavcodec/vulkan/ffv1_enc.comp.glsl | 13 +- libavcodec/vulkan/ffv1_enc_setup.comp.glsl | 12 +- libavcodec/vulkan/ffv1_enc_sort32.comp.glsl | 223 +++++++++++++++------------- 4 files changed, 135 insertions(+), 118 deletions(-) diff --git a/libavcodec/ffv1enc_vulkan.c b/libavcodec/ffv1enc_vulkan.c index 14f7d2e5dc..f91bd0a6c1 100644 --- a/libavcodec/ffv1enc_vulkan.c +++ b/libavcodec/ffv1enc_vulkan.c @@ -361,7 +361,7 @@ static int vulkan_encode_ffv1_submit_frame(AVCodecContext *avctx, if (f->remap_mode) { if (fv->is_float32) { - /* Per (slice, plane): [units : max_pixels*2 uints] + [bitmap : max_pixels uints]. */ + /* Per slice: [units : 4*max_pixels*2 uints] + [bitmaps : 4*max_pixels uints]. */ remap_data_size = 4*fv->max_pixels_per_slice*3*sizeof(uint32_t); } else { const AVPixFmtDescriptor *desc = av_pix_fmt_desc_get(fv->s.frames->sw_format); @@ -1003,7 +1003,8 @@ static int init_sort32_shader(AVCodecContext *avctx, VkSpecializationInfo *sl) VulkanEncodeFFv1Context *fv = avctx->priv_data; FFVulkanShader *shd = &fv->sort32; - uint32_t wg_x = FFMIN(fv->max_pixels_per_slice, 256); + uint32_t wg_x = FFMIN3(fv->max_pixels_per_slice, 1024, + fv->s.props.properties.limits.maxComputeWorkGroupSize[0]); ff_vk_shader_load(shd, VK_SHADER_STAGE_COMPUTE_BIT, sl, (uint32_t []) { wg_x, 1, 1 }, 0); diff --git a/libavcodec/vulkan/ffv1_enc.comp.glsl b/libavcodec/vulkan/ffv1_enc.comp.glsl index f510266d7b..c59ad5527f 100644 --- a/libavcodec/vulkan/ffv1_enc.comp.glsl +++ b/libavcodec/vulkan/ffv1_enc.comp.glsl @@ -252,16 +252,13 @@ ivec4 load_components(uint slice_idx, in SliceContext sc, ivec2 pos) ivec4 pix; #ifdef FLOAT if (c_bits >= 32) { - /* 32-bit float: per-pixel-position bitmap lookup. The bitmap region - * follows the units region in the same buffer. */ + /* 32-bit float: per-pixel-position bitmap lookup. The bitmaps of + * the planes follow the units of the planes in the same buffer. */ ivec2 rel = pos - sc.slice_pos; uint pixel_idx = uint(rel.x + sc.slice_dim.x*rel.y); - uint plane_stride = max_pixels_per_slice*3u; - for (int i = 0; i < color_planes; i++) { - uint base = (slice_idx*4u + uint(i))*plane_stride - + max_pixels_per_slice*2u; - pix[i] = int(fltmap[base + pixel_idx]); - } + uint base = (slice_idx*12u + 8u)*max_pixels_per_slice; + for (int i = 0; i < color_planes; i++) + pix[i] = int(fltmap[base + uint(i)*max_pixels_per_slice + pixel_idx]); } else { /* 16-bit float: value-indexed lookup. Source view is r16_uint so * imageLoad returns the raw fp16 bit pattern in .x. */ diff --git a/libavcodec/vulkan/ffv1_enc_setup.comp.glsl b/libavcodec/vulkan/ffv1_enc_setup.comp.glsl index 0b28dd4003..d02f982997 100644 --- a/libavcodec/vulkan/ffv1_enc_setup.comp.glsl +++ b/libavcodec/vulkan/ffv1_enc_setup.comp.glsl @@ -148,15 +148,15 @@ void encode_float32_remap(uint slice_idx, inout SliceContext sc) const uint slice_w = uint(sc.slice_dim.x); const uint slice_h = uint(sc.slice_dim.y); const uint pixel_num = slice_w * slice_h; - const uint plane_stride = max_pixels_per_slice*3u; + const uint slice_base = slice_idx*12u*max_pixels_per_slice; const int64_t end = int64_t(0xFFFFFFFFu); for (int p = 0; p < color_planes; p++) { - /* Layout: per (slice, plane) we have units (max_pixels*8 bytes) - * followed by bitmap (max_pixels*4 bytes). The units region is - * read-only here, the bitmap region is written. */ - const uint plane_base = (slice_idx*4u + uint(p))*plane_stride; - const uint bitmap_base = plane_base + max_pixels_per_slice*2u; + /* Layout: per slice, the sorted units of each plane (max_pixels*8 + * bytes), then the bitmaps of each plane (max_pixels*4 bytes). The + * units are read-only here, the bitmap is written. */ + const uint plane_base = slice_base + uint(p)*2u*max_pixels_per_slice; + const uint bitmap_base = slice_base + (8u + uint(p))*max_pixels_per_slice; for (int i = 0; i < NB_CONTEXTS*CONTEXT_SIZE; i++) rc_state[i] = uint8_t(128); diff --git a/libavcodec/vulkan/ffv1_enc_sort32.comp.glsl b/libavcodec/vulkan/ffv1_enc_sort32.comp.glsl index 4d40d94577..754f34e53d 100644 --- a/libavcodec/vulkan/ffv1_enc_sort32.comp.glsl +++ b/libavcodec/vulkan/ffv1_enc_sort32.comp.glsl @@ -22,6 +22,10 @@ #pragma shader_stage(compute) #extension GL_GOOGLE_include_directive : require +#extension GL_KHR_shader_subgroup_basic : require +#extension GL_KHR_shader_subgroup_ballot : require +#extension GL_KHR_shader_subgroup_arithmetic : require +#extension GL_KHR_shader_subgroup_shuffle : require #define SB_QUALI readonly #include "common.glsl" @@ -29,125 +33,140 @@ layout (set = 1, binding = 1) uniform uimage2D src[]; -layout (set = 1, binding = 2, scalar) buffer fltmap_buf { - uint fltmap[]; +layout (set = 1, binding = 2, scalar) workgroupcoherent buffer fltmap_buf { + u32vec2 fltmap[]; }; -/* The shared fltmap_buf is laid out per (slice, plane) as a - * max_pixels_per_slice*3 uint block, where the first - * max_pixels_per_slice*2 entries hold interleaved (val, ndx) pairs and - * the trailing [max_pixels_per_slice] entries are the bitmap region used - * by the setup/encode shaders. Padding past pixel_num is the sentinel - * (UINT32_MAX, UINT32_MAX) so it sorts at the end. */ +/* Per slice, fltmap_buf holds the sorted (val, ndx) pairs of each plane, + * max_pixels_per_slice each, followed by the bitmaps of each plane, which + * the setup shader fills after the sort, so they serve as its scratch. */ -/* Per-workgroup bitonic-sort buffer. Limits a slice's pow2 size; large - * slices fall back to working in global memory */ -shared u32vec2 smem[8192]; +#define RADIX_BITS 4 +#define RADIX_SIZE 16 -void main(void) -{ - const uint slice_idx = gl_WorkGroupID.y*gl_NumWorkGroups.x + gl_WorkGroupID.x; - uvec2 img_size = imageSize(src[0]); +shared uint cnt[RADIX_SIZE][gl_WorkGroupSize.x / 4]; +shared uint hist[RADIX_SIZE]; - uint sxs = slice_coord(img_size.x, gl_WorkGroupID.x + 0, - gl_NumWorkGroups.x, 0); - uint sxe = slice_coord(img_size.x, gl_WorkGroupID.x + 1, - gl_NumWorkGroups.x, 0); - uint sys = slice_coord(img_size.y, gl_WorkGroupID.y + 0, - gl_NumWorkGroups.y, 0); - uint sye = slice_coord(img_size.y, gl_WorkGroupID.y + 1, - gl_NumWorkGroups.y, 0); +uint slice_w, sxs, sys; - uint slice_w = sxe - sxs; - uint slice_h = sye - sys; - uint pixel_num = slice_w * slice_h; +u32vec2 load_pixel(uint i, int p) +{ + uint y = i / slice_w; + uint x = i - y*slice_w; + uint v = imageLoad(src[p], ivec2(sxs + x, sys + y))[0]; + if (remap_mode == 2) + v = ((v & 0x80000000u) != 0u) ? v : (v ^ 0x7FFFFFFFu); + return u32vec2(v, i); +} - /* Round up to next pow2 for bitonic sort */ - uint N = 1; - while (N < pixel_num) - N <<= 1; - N = max(N, 2); - if (N > max_pixels_per_slice) - N = max_pixels_per_slice; +/* Lanes of the subgroup whose element has the digit d */ +uvec4 digit_lanes(bool live, uint d) +{ + uvec4 lanes = subgroupBallot(live); + [[unroll]] for (int k = 0; k < RADIX_BITS; k++) { + uvec4 b = subgroupBallot(live && ((d >> k) & 1u) != 0u); + lanes &= ((d >> k) & 1u) != 0u ? b : ~b; + } + return lanes; +} - const uint plane_stride = max_pixels_per_slice*3u; - const bool use_smem = N <= 8192u; +/* LSD radix sort, 4 bits per pass, between the two buffers. Each subgroup + * owns a block of rows of elements, one per lane, ranked with ballots. */ +void radix_sort(int p, uint n, uint src, uint dst) +{ + const uint sg = gl_SubgroupID; + const uint lane = gl_SubgroupInvocationID; + const uint S = min(gl_SubgroupSize, gl_WorkGroupSize.x); + const uint rows = (n + gl_WorkGroupSize.x - 1) / gl_WorkGroupSize.x; + const uint block = sg*rows*S; - for (int p = 0; p < color_planes; p++) { - uint base = (slice_idx*4u + uint(p))*plane_stride; + for (uint shift = 0; shift < 32; shift += RADIX_BITS) { + for (uint v = lane; v < RADIX_SIZE; v += S) + cnt[v][sg] = 0; + if (gl_LocalInvocationIndex < RADIX_SIZE) + hist[gl_LocalInvocationIndex] = 0; + barrier(); - /* Load pixels */ - for (uint i = gl_LocalInvocationIndex; i < N; - i += gl_WorkGroupSize.x * gl_WorkGroupSize.y) { - uint v, ndx; - if (i < pixel_num) { - uint y = i / slice_w; - uint x = i - y*slice_w; - v = imageLoad(src[p], ivec2(sxs + x, sys + y))[0]; - if (remap_mode == 2) - v = ((v & 0x80000000u) != 0u) ? v : (v ^ 0x7FFFFFFFu); - ndx = i; - } else { - v = 0xFFFFFFFFu; - ndx = 0xFFFFFFFFu; - } - if (use_smem) { - smem[i] = u32vec2(v, ndx); - } else { - fltmap[base + 2u*i + 0u] = v; - fltmap[base + 2u*i + 1u] = ndx; + /* Count of each digit per block and in total */ + for (uint m = 0; m < rows; m++) { + const uint i = block + m*S + lane; + const bool live = i < n; + const u32vec2 e = !live ? u32vec2(0) : shift == 0 ? + load_pixel(i, p) : fltmap[src + i]; + const uint d = (e.x >> shift) & (RADIX_SIZE - 1); + const uvec4 lanes = digit_lanes(live, d); + if (live && subgroupBallotExclusiveBitCount(lanes) == 0) { + atomicAdd(cnt[d][sg], subgroupBallotBitCount(lanes)); + atomicAdd(hist[d], subgroupBallotBitCount(lanes)); } } barrier(); - if (!use_smem) memoryBarrierBuffer(); - /* Bitonic sort of the (val, ndx) pairs. */ - for (uint k = 2; k <= N; k <<= 1) { - for (uint j = k >> 1; j > 0; j >>= 1) { - for (uint i = gl_LocalInvocationIndex; i < N; - i += gl_WorkGroupSize.x * gl_WorkGroupSize.y) { - uint partner = i ^ j; - if (partner > i) { - bool ascending = (i & k) == 0; - u32vec2 a, b; - if (use_smem) { - a = smem[i]; - b = smem[partner]; - } else { - a = u32vec2(fltmap[base + 2u*i + 0u], - fltmap[base + 2u*i + 1u]); - b = u32vec2(fltmap[base + 2u*partner + 0u], - fltmap[base + 2u*partner + 1u]); - } - bool a_gt_b = (a.x > b.x) || - (a.x == b.x && a.y > b.y); - if (a_gt_b == ascending) { - if (use_smem) { - smem[i] = b; - smem[partner] = a; - } else { - fltmap[base + 2u*i + 0u] = b.x; - fltmap[base + 2u*i + 1u] = b.y; - fltmap[base + 2u*partner + 0u] = a.x; - fltmap[base + 2u*partner + 1u] = a.y; - } - } - } - } - barrier(); - if (!use_smem) memoryBarrierBuffer(); + /* Offset of each digit per block: the digit's base plus its count + * in the blocks before */ + for (uint v = sg; v < RADIX_SIZE; v += gl_NumSubgroups) { + uint carry = 0; + for (uint w = 0; w < v; w++) + carry += hist[w]; + for (uint c = 0; c < gl_NumSubgroups; c += S) { + const bool has = c + lane < gl_NumSubgroups; + const uint x = has ? cnt[v][c + lane] : 0; + const uint ex = subgroupExclusiveAdd(x); + if (has) + cnt[v][c + lane] = carry + ex; + carry += subgroupAdd(x); } } + barrier(); - /* Write sorted pairs back to global */ - if (use_smem) { - for (uint i = gl_LocalInvocationIndex; i < N; - i += gl_WorkGroupSize.x * gl_WorkGroupSize.y) { - u32vec2 u = smem[i]; - fltmap[base + 2u*i + 0u] = u.x; - fltmap[base + 2u*i + 1u] = u.y; - } - barrier(); + /* Scatter each row from the offsets, advancing them */ + for (uint m = 0; m < rows; m++) { + const uint i = block + m*S + lane; + const bool live = i < n; + const u32vec2 e = !live ? u32vec2(0) : shift == 0 ? + load_pixel(i, p) : fltmap[src + i]; + const uint d = (e.x >> shift) & (RADIX_SIZE - 1); + const uvec4 lanes = digit_lanes(live, d); + const uint before = subgroupBallotExclusiveBitCount(lanes); + uint pos = 0; + if (live && before == 0) + pos = atomicAdd(cnt[d][sg], subgroupBallotBitCount(lanes)); + pos = subgroupShuffle(pos, subgroupBallotFindLSB(lanes)) + before; + if (live) + fltmap[dst + pos] = e; } + controlBarrier(gl_ScopeWorkgroup, gl_ScopeWorkgroup, + gl_StorageSemanticsShared | gl_StorageSemanticsBuffer, + gl_SemanticsAcquireRelease); + + const uint t = src; + src = dst; + dst = t; } } + +void main(void) +{ + const uint slice_idx = gl_WorkGroupID.y*gl_NumWorkGroups.x + gl_WorkGroupID.x; + uvec2 img_size = imageSize(src[0]); + + sxs = slice_coord(img_size.x, gl_WorkGroupID.x + 0, + gl_NumWorkGroups.x, 0); + uint sxe = slice_coord(img_size.x, gl_WorkGroupID.x + 1, + gl_NumWorkGroups.x, 0); + sys = slice_coord(img_size.y, gl_WorkGroupID.y + 0, + gl_NumWorkGroups.y, 0); + uint sye = slice_coord(img_size.y, gl_WorkGroupID.y + 1, + gl_NumWorkGroups.y, 0); + + slice_w = sxe - sxs; + uint slice_h = sye - sys; + uint pixel_num = slice_w * slice_h; + + const uint slice_base = slice_idx*6u*max_pixels_per_slice; + const uint scratch = slice_base + 4u*max_pixels_per_slice; + + for (int p = 0; p < color_planes; p++) + radix_sort(p, pixel_num, slice_base + uint(p)*max_pixels_per_slice, + scratch); +} -- To stop receiving notification emails like this one, please contact [email protected]. _______________________________________________ ffmpeg-cvslog mailing list -- [email protected] To unsubscribe send an email to [email protected]
