From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org [79.124.17.100]) by master.gitmailbox.com (Postfix) with ESMTP id 1B7AC491A9 for ; Mon, 5 Feb 2024 12:03:18 +0000 (UTC) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 0E4CF68D0EF; Mon, 5 Feb 2024 14:03:17 +0200 (EET) Received: from EUR04-DB3-obe.outbound.protection.outlook.com (mail-db3eur04olkn2054.outbound.protection.outlook.com [40.92.74.54]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 31FD068D0EF for ; Mon, 5 Feb 2024 14:03:10 +0200 (EET) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=SxpPYU2qdWGxadXCVRGBPZxW5erb4MkehY8PPRMepKNFq+gTJQfCvMvJGKE39V3JVuSyW4ScvyxT4Y1SqP6DXBFD/BIiUqv7NYrJFQmRIRmMes4xn3X8qK54xCgmPnpcnn5Pup+uqHABiLAnXroYw7Cu+20VMsMQufCBJe61RD5l9Q7kR8Vp/Qm61bzJYB1bZR/GCcptksYJuzhyVF24Ai2LDUxymHBRHJM4DcuK8Su/ViyhKHDEAFLRVYqZG+/zhx22s3tCNh4TafsKxZ3jCZXqKuLpKDIwGm3Hr36y3IBdTfXIqP5VQUVANQ8l+0i3YdE+5llLbNe9JZcsoveyIg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=4L7VqaqTQiHZ8lUYeDg3ijtS5FMOxWN3KSYo+FFghJw=; b=eaVqFOb0D8ZGonfjg4BX4miPobCcJTYMbjrHGfTfrWrE8O2I85SQ8aHOgKvkHG7HKag0ZSIKSKjTjjLcvutzsuusPQ0pu8LHARp5IygU2e6mVpNKglq8ezYITeX4UAHOdorBbaTYjOI9ShiGpC9dFo4QjhZqWvdQGO/nzSNtV7SOs+lbgw7+9f+F8PEcyweRoDa3wqZ3Ioa9s7evm1Xr46GIn/hYXgkAQMqTl+CqJCEuF3UCl226tFMBz9cN5MpkMUPuPC+jixQ4ObqJ/5KVfUGqTFAplr+MAgeq5g0oXZPDCMnReeKoH/u8y3ALgEOIkhImzw2FAKpKEtpBJJA+5Q== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=none; dmarc=none; dkim=none; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=outlook.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=4L7VqaqTQiHZ8lUYeDg3ijtS5FMOxWN3KSYo+FFghJw=; b=mOSeU7jr1krzN8v6l6CvwLM25c6y4UqyWUlx05lfmLLfPhjNIeVEAZT1fjEDMJjYS+T270+kH0TaxS0mzycSuH5gB2fbYwaAtH9zizHxIqYmBDpoukN+CpGLHf+y23Hf51VxM7HVTiGkjxooe1RML4ZuQcf2AmHHwklTOsAoS7Jzo3Pi6CCkR2cjDmTbaqrepAJCKmtrft0pLKzS+40bbGo2xvxdz4TZkldzZWQ00TrduNfktmGrrAkck6g3XmdrCpw9wMM3z6bViu58ZH2RpvmImUalJXlo65ktS6xrrtFRfi0UlUjr9LoldVc1PaF65MafGeWkGSAwKivjQN4kGw== Received: from AS8P250MB0744.EURP250.PROD.OUTLOOK.COM (2603:10a6:20b:541::14) by AS8P250MB0251.EURP250.PROD.OUTLOOK.COM (2603:10a6:20b:37e::14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7249.34; Mon, 5 Feb 2024 12:03:02 +0000 Received: from AS8P250MB0744.EURP250.PROD.OUTLOOK.COM ([fe80::65aa:deb0:a18e:d48d]) by AS8P250MB0744.EURP250.PROD.OUTLOOK.COM ([fe80::65aa:deb0:a18e:d48d%5]) with mapi id 15.20.7249.032; Mon, 5 Feb 2024 12:03:01 +0000 Message-ID: Date: Mon, 5 Feb 2024 13:04:54 +0100 User-Agent: Mozilla Thunderbird Content-Language: en-US To: ffmpeg-devel@ffmpeg.org References: <20240205052724.26862-1-connorbworley@gmail.com> <20240205052724.26862-2-connorbworley@gmail.com> From: Andreas Rheinhardt In-Reply-To: <20240205052724.26862-2-connorbworley@gmail.com> X-TMN: [7/reeUwmJ+IWQHas1bWb+zRXNJjKmCNe3snc93ploHI=] X-ClientProxiedBy: ZR0P278CA0027.CHEP278.PROD.OUTLOOK.COM (2603:10a6:910:1c::14) To AS8P250MB0744.EURP250.PROD.OUTLOOK.COM (2603:10a6:20b:541::14) X-Microsoft-Original-Message-ID: MIME-Version: 1.0 X-MS-Exchange-MessageSentRepresentingType: 1 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: AS8P250MB0744:EE_|AS8P250MB0251:EE_ X-MS-Office365-Filtering-Correlation-Id: 5f827c98-7725-41d1-29e1-08dc264266e4 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: QsOyXPDt5n2IhJJVKu5JUzMy7VOTMyp3dd2QH8HHZ+dbeq3tPMQPA7w42LkS1cXOrNXoj3Vyxv/icIKqtZ2CbhefB7X3EQHBCkcddm6AXi6KIJo2wUvuR1cgpQpBF3/ndoeeQVZuQDyCsT9WFRXw3Gyc7kgbTh+cDQ1iDryiQNkHwRSpZj7O0MPfjr6qBg/v09H993Wk0f0i1Feur958aizKwwUGdFo1hlj+t5Il28D8urUc2DjmgFmLHISbok9oHpALfxJTl0vkmNmEExPEXXWLhIWm6NOx+Znk0Ff+GsPWZsk8Ijp4/W19lQmwKjK5j+buxX8EkT7syMbI5pqRKRQ1gNDWNhGt1X8fc2Iq3I3szNlMvl7oHbVxwPVe1Wpsb1SyJ4BvG/gpEz/nzto4A7n68a5rNdnvBnjm7FJ4ySb/wUXV8EE3UV83xBGfgVDOXJC0wS0mCvqzS2pdxg3j7J2J7f+FmvZFKf2uidx56eR+IW2BJQCRGDRjIQ6abdTzUUBOM05KQBfC6Uqa6jvox23EESPCXOdgtN+7sv34YAF1Z3uPOlGD9BXazSkx8zc0 X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?VEptNmZFZXV0dzRlT1JKMzVBTkkxL0lSeGhBazdqNXhIVGJ5MkFDaEFSMzJm?= =?utf-8?B?TlNHVEp2dmFqY2dZd2hWdjRzZy9VeXV0S1haSEtycXhGVUJRS0I4L1VmUXBT?= =?utf-8?B?VUJzV1pYUWhzTXhQTTRrRlQ2Ykg5c05UcFdwdE05a3JtZ3dOVHJpMTByWHRl?= =?utf-8?B?MHMxUmdPLzhITm0vRExlOTZEYW9EeVorU3Bhc1BFSko2ZGhhTVFad09qMk1Y?= =?utf-8?B?Wis0NmNVQ2tZOVdMWWxBckF6d0ovWG1RckRBZDJiSThBYUJqa2lHMTdiTEU5?= =?utf-8?B?QlB0VmViU2JOM3dtMUtIc2Z5WkhOQm94OHhJY1ZoT2NnTTNYUzQxTU1mM1Ir?= =?utf-8?B?b2plRkdYUVlhYlFmdUJLRmQ0d2FQY2JUekFpNmVlelpxOXVKaFpHVzRZMUxP?= =?utf-8?B?RUJCOWl3bU4yQ1dGMWMxenBsSFNncWFpeVFrazU4YUV3NStuWkRldkIzOFZo?= =?utf-8?B?bzJxMEVoRVJsd094Z0I1RGduV3IwWS92SGZyTFdydzk5UmFVR1M2c0ZwTE5C?= =?utf-8?B?Y3hDeUJRUTFkeU5lUDB3L3NUZXQ1c2ZKRjk4YThQdjl3eGczcitWK2IzRXU5?= =?utf-8?B?WXBMelo2dEF2b3MycXJkL096cjBQWDVKTHUxdTJoNm9Ob0t1TWJtYW13YzBz?= =?utf-8?B?cEtkSkxGK0FNTWIvUThqQTcvZlZMMFZpWFNTOXNiSUMzc3hXYmJCRU1SWGgr?= =?utf-8?B?Ky9mZ3NMeDcyYUxuUXhYZSt0ZGhEaGczVUdrQVNyVEpqbzRZNmFlVUFrT2ZB?= =?utf-8?B?dzVqamdwQWNVTmRqRmVFRG9NKzZGNHBFVzJ6WEpmWnBhM09yaVNaVGJsTitr?= =?utf-8?B?U3FtTUVuMU5tOWM3NldtUDlCNDAyTC9QZ21ibWNGZitXaHV3djlQN0ErbU00?= =?utf-8?B?cEpSSGhMVndhTWM5UHZ1dU9SUjBuSEQ0SXZkbDl2T3RzN1R4MDJRQndQNFBF?= =?utf-8?B?eTFsUzNoR1VLNnk5dmhleUxZR2I4bjlEMHFpazFmY3pOTCthNWxNVFdqVnp1?= =?utf-8?B?MEtRZjAyTDRGY0ZWekdnVVd6YmpsQXNhQU1kNDQraEJNL1RzVmIrd0VraWhq?= =?utf-8?B?dEdYRE1GKy9uQjRMOHM5QWJSbTBRaFBrSzZWYnl1eTlodmVTVHFrNXVHVkUx?= =?utf-8?B?RHlKNTFkcmJVSktZQnNQQUQ4K1h4OXBSOFRHNXptWFk4SnhpTGpQZ1UrMEZF?= =?utf-8?B?RU50Qlk3QUI4UmJ1TDUzb3prZSs5M3VDcVFlNkYyTlR6eGMrYnYzNWhBRkdL?= =?utf-8?B?QnZBL2NrdlVRNTgyT0xvUWtQdWw5VGNCTU1qQTA1b1k2OHp2REhYVE9pa1JG?= =?utf-8?B?bks0RkxvTEJwNDdydGs0UG12dnRBVk5LamVXTWZpVzhtSTRIUDVrU1VvT050?= =?utf-8?B?dC9LczVwNS90ZGJCbDREMEJNUnE5cVRJeDFuOUY1akJoamhBUlNiWEh3Z0NV?= =?utf-8?B?MlpQZDBHNHBoZnVXVHdvL1hIQmFUQnBQbk8rMDluaG1DRHloVXZYbVU4SzJt?= =?utf-8?B?UFk5NzV5dTQ2SllVb3JDTHEzbDlwa1FIS1EwK3c3RmtSUzNWTHdhb2p6N0Ir?= =?utf-8?B?T2NXbGxvNFcvaXgvbGxLV3hBemxlQmcwS3JlbGloWUNQTVRQUk1aQkxlejJn?= =?utf-8?B?TlFZUDF1UWhRU1Fsc2V5alhlc2xPK3NTbmJqTEZMVVZzRmdXSFZjOU1nZ3Bl?= =?utf-8?Q?3mqjzcB2i5t1N2+0lbkJ?= X-OriginatorOrg: outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: 5f827c98-7725-41d1-29e1-08dc264266e4 X-MS-Exchange-CrossTenant-AuthSource: AS8P250MB0744.EURP250.PROD.OUTLOOK.COM X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 05 Feb 2024 12:03:01.7671 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: 84df9e7f-e9f6-40af-b435-aaaaaaaaaaaa X-MS-Exchange-CrossTenant-RMS-PersistedConsumerOrg: 00000000-0000-0000-0000-000000000000 X-MS-Exchange-Transport-CrossTenantHeadersStamped: AS8P250MB0251 Subject: Re: [FFmpeg-devel] [PATCH 2/2] lavc/dxvenc: migrate DXT1 encoder to lavu hashtable X-BeenThere: ffmpeg-devel@ffmpeg.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: FFmpeg development discussions and patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: FFmpeg development discussions and patches Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" Archived-At: List-Archive: List-Post: Connor Worley: > Offers a modest performance gain due to the switch from naive linear > probling to robin hood. How much would one gain if the hash function knew that key_size and val_size are four? > > Signed-off-by: Connor Worley > --- > libavcodec/dxvenc.c | 121 +++++++++++++------------------------------- > 1 file changed, 35 insertions(+), 86 deletions(-) > > diff --git a/libavcodec/dxvenc.c b/libavcodec/dxvenc.c > index b274175689..e17b3b2c36 100644 > --- a/libavcodec/dxvenc.c > +++ b/libavcodec/dxvenc.c > @@ -21,7 +21,7 @@ > > #include > > -#include "libavutil/crc.h" > +#include "libavutil/hashtable.h" > #include "libavutil/imgutils.h" > #include "libavutil/opt.h" > > @@ -44,69 +44,6 @@ enum DXVTextureFormat { > DXV_FMT_DXT1 = MKBETAG('D', 'X', 'T', '1'), > }; > > -typedef struct HTEntry { > - uint32_t key; > - uint32_t pos; > -} HTEntry; > - > -static void ht_init(HTEntry *ht) > -{ > - for (size_t i = 0; i < LOOKBACK_HT_ELEMS; i++) { > - ht[i].pos = -1; > - } > -} > - > -static uint32_t ht_lookup_and_upsert(HTEntry *ht, const AVCRC *hash_ctx, > - uint32_t key, uint32_t pos) > -{ > - uint32_t ret = -1; > - size_t hash = av_crc(hash_ctx, 0, (uint8_t*)&key, 4) % LOOKBACK_HT_ELEMS; > - for (size_t i = hash; i < hash + LOOKBACK_HT_ELEMS; i++) { > - size_t wrapped_index = i % LOOKBACK_HT_ELEMS; > - HTEntry *entry = &ht[wrapped_index]; > - if (entry->key == key || entry->pos == -1) { > - ret = entry->pos; > - entry->key = key; > - entry->pos = pos; > - break; > - } > - } > - return ret; > -} > - > -static void ht_delete(HTEntry *ht, const AVCRC *hash_ctx, > - uint32_t key, uint32_t pos) > -{ > - HTEntry *removed_entry = NULL; > - size_t removed_hash; > - size_t hash = av_crc(hash_ctx, 0, (uint8_t*)&key, 4) % LOOKBACK_HT_ELEMS; > - > - for (size_t i = hash; i < hash + LOOKBACK_HT_ELEMS; i++) { > - size_t wrapped_index = i % LOOKBACK_HT_ELEMS; > - HTEntry *entry = &ht[wrapped_index]; > - if (entry->pos == -1) > - return; > - if (removed_entry) { > - size_t candidate_hash = av_crc(hash_ctx, 0, (uint8_t*)&entry->key, 4) % LOOKBACK_HT_ELEMS; > - if ((wrapped_index > removed_hash && (candidate_hash <= removed_hash || candidate_hash > wrapped_index)) || > - (wrapped_index < removed_hash && (candidate_hash <= removed_hash && candidate_hash > wrapped_index))) { > - *removed_entry = *entry; > - entry->pos = -1; > - removed_entry = entry; > - removed_hash = wrapped_index; > - } > - } else if (entry->key == key) { > - if (entry->pos <= pos) { > - entry->pos = -1; > - removed_entry = entry; > - removed_hash = wrapped_index; > - } else { > - return; > - } > - } > - } > -} > - > typedef struct DXVEncContext { > AVClass *class; > > @@ -123,10 +60,8 @@ typedef struct DXVEncContext { > enum DXVTextureFormat tex_fmt; > int (*compress_tex)(AVCodecContext *avctx); > > - const AVCRC *crc_ctx; > - > - HTEntry color_lookback_ht[LOOKBACK_HT_ELEMS]; > - HTEntry lut_lookback_ht[LOOKBACK_HT_ELEMS]; > + AVHashtableContext color_ht; > + AVHashtableContext lut_ht; > } DXVEncContext; > > /* Converts an index offset value to a 2-bit opcode and pushes it to a stream. > @@ -161,27 +96,32 @@ static int dxv_compress_dxt1(AVCodecContext *avctx) > DXVEncContext *ctx = avctx->priv_data; > PutByteContext *pbc = &ctx->pbc; > uint32_t *value; > - uint32_t color, lut, idx, color_idx, lut_idx, prev_pos, state = 16, pos = 2, op = 0; > + uint32_t color, lut, idx, color_idx, lut_idx, prev_pos, state = 16, pos = 0, op = 0; > > - ht_init(ctx->color_lookback_ht); > - ht_init(ctx->lut_lookback_ht); > + av_hashtable_clear(&ctx->color_ht); > + av_hashtable_clear(&ctx->lut_ht); > > bytestream2_put_le32(pbc, AV_RL32(ctx->tex_data)); > + av_hashtable_set(&ctx->color_ht, ctx->tex_data, &pos); > + pos++; > bytestream2_put_le32(pbc, AV_RL32(ctx->tex_data + 4)); > - > - ht_lookup_and_upsert(ctx->color_lookback_ht, ctx->crc_ctx, AV_RL32(ctx->tex_data), 0); > - ht_lookup_and_upsert(ctx->lut_lookback_ht, ctx->crc_ctx, AV_RL32(ctx->tex_data + 4), 1); > + av_hashtable_set(&ctx->lut_ht, ctx->tex_data + 4, &pos); > + pos++; > > while (pos + 2 <= ctx->tex_size / 4) { > idx = 0; > + color_idx = 0; > + lut_idx = 0; > > color = AV_RL32(ctx->tex_data + pos * 4); > - prev_pos = ht_lookup_and_upsert(ctx->color_lookback_ht, ctx->crc_ctx, color, pos); > - color_idx = prev_pos != -1 ? pos - prev_pos : 0; > + if (av_hashtable_get(&ctx->color_ht, &color, &prev_pos)) > + color_idx = pos - prev_pos; > + av_hashtable_set(&ctx->color_ht, &color, &pos); > + > if (pos >= LOOKBACK_WORDS) { > uint32_t old_pos = pos - LOOKBACK_WORDS; > - uint32_t old_color = AV_RL32(ctx->tex_data + old_pos * 4); > - ht_delete(ctx->color_lookback_ht, ctx->crc_ctx, old_color, old_pos); > + if (av_hashtable_get(&ctx->color_ht, ctx->tex_data + old_pos * 4, &prev_pos) && prev_pos <= old_pos) > + av_hashtable_delete(&ctx->color_ht, ctx->tex_data + old_pos * 4); > } > pos++; > > @@ -190,13 +130,14 @@ static int dxv_compress_dxt1(AVCodecContext *avctx) > idx = color_idx; > } else { > idx = 0; > - prev_pos = ht_lookup_and_upsert(ctx->lut_lookback_ht, ctx->crc_ctx, lut, pos); > - lut_idx = prev_pos != -1 ? pos - prev_pos : 0; > + if (av_hashtable_get(&ctx->lut_ht, &lut, &prev_pos)) > + lut_idx = pos - prev_pos; > + av_hashtable_set(&ctx->lut_ht, &lut, &pos); > } > if (pos >= LOOKBACK_WORDS) { > uint32_t old_pos = pos - LOOKBACK_WORDS; > - uint32_t old_lut = AV_RL32(ctx->tex_data + old_pos * 4); > - ht_delete(ctx->lut_lookback_ht, ctx->crc_ctx, old_lut, old_pos); > + if (av_hashtable_get(&ctx->lut_ht, ctx->tex_data + old_pos * 4, &prev_pos) && prev_pos <= old_pos) > + av_hashtable_delete(&ctx->lut_ht, ctx->tex_data + old_pos * 4); > } > pos++; > > @@ -298,10 +239,15 @@ static av_cold int dxv_init(AVCodecContext *avctx) > return AVERROR(ENOMEM); > } > > - ctx->crc_ctx = av_crc_get_table(AV_CRC_32_IEEE); > - if (!ctx->crc_ctx) { > - av_log(avctx, AV_LOG_ERROR, "Could not initialize CRC table.\n"); > - return AVERROR_BUG; > + ret = av_hashtable_init(&ctx->color_ht, sizeof(uint32_t), sizeof(uint32_t), LOOKBACK_HT_ELEMS); > + if (ret < 0) { > + av_log(avctx, AV_LOG_ERROR, "Could not initialize color lookback table.\n"); > + return ret; > + } > + ret = av_hashtable_init(&ctx->lut_ht, sizeof(uint32_t), sizeof(uint32_t), LOOKBACK_HT_ELEMS); > + if (ret < 0) { > + av_log(avctx, AV_LOG_ERROR, "Could not initialize LUT lookback table.\n"); These av_logs are pointless. > + return ret; > } > > return 0; > @@ -313,6 +259,9 @@ static av_cold int dxv_close(AVCodecContext *avctx) > > av_freep(&ctx->tex_data); > > + av_hashtable_destroy(&ctx->color_ht); > + av_hashtable_destroy(&ctx->lut_ht); > + > return 0; > } > _______________________________________________ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org https://ffmpeg.org/mailman/listinfo/ffmpeg-devel To unsubscribe, visit link above, or email ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".