From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: <ffmpeg-devel-bounces@ffmpeg.org> Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org [79.124.17.100]) by master.gitmailbox.com (Postfix) with ESMTPS id B88044CB10 for <ffmpegdev@gitmailbox.com>; Sat, 12 Apr 2025 15:12:17 +0000 (UTC) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id A11ED68A56A; Sat, 12 Apr 2025 18:12:13 +0300 (EEST) Received: from mail-pj1-f42.google.com (mail-pj1-f42.google.com [209.85.216.42]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 409FD68A56A for <ffmpeg-devel@ffmpeg.org>; Sat, 12 Apr 2025 18:12:06 +0300 (EEST) Received: by mail-pj1-f42.google.com with SMTP id 98e67ed59e1d1-306b602d2ffso3173221a91.0 for <ffmpeg-devel@ffmpeg.org>; Sat, 12 Apr 2025 08:12:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1744470724; x=1745075524; darn=ffmpeg.org; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :message-id:from:to:cc:subject:date:message-id:reply-to; bh=XruWwCg5prfES2lmTUQQsOXvdFfFmQyO/iGhPwSrdh0=; b=lSmL68oY14htGl4G1KexxOagzbBBiP4jwDzoHak21jGJeF72gAZa8JqgtPrO7xPAlp CDPDsysGp+tlW6osmpwdm1u+vWw7SL1ATkh4xstwcFWG/nX9uMHyDretCNvNZjLost/j yUsxEjWY+sE6Tin2Q8DhMsp9vG3skd8bJIwss3Acmyh6pSTtpgf9aNWQJVaGXYGPRjUg b5QMDz4SgaqLAo+3D1dqZZTNjGh/jk/sBYRIqFaZciBn9P2kUZKtPWUR1X25bVifKrxg WpKGnsv3QT4rg//cNOLyDsAlXpkozLXvsbX5LtYRdAdSLCD2Yk98lKgYj9n410VvPS5V fdtg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1744470724; x=1745075524; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=XruWwCg5prfES2lmTUQQsOXvdFfFmQyO/iGhPwSrdh0=; b=tPddr/urIYWBlwiDEqHTFaZN5A9VweVoXzDM7QbgrJqsny5qa60fTD3DH7MbqYrid+ qiC+goFpsgH9HpO74BjX00vQZ77H0Pa++NxP++PSTi1HYGZbdcmxJvRjKBElIPvf+uUy XZWSo95TNaxDGWYmkhMDLei3pH6vRh1O4bvEUVcfJg+hLr8FwIyIrSk7D2blwRwSdshl ICjZzT7r3EvOtRaqKEVXUNTsYNASSLjGtAiPikN02zgyFtt8FgJzhgOteX2SkYia/tVF ghNalK5iLjcbVEDHc5QoChr1Mpz2zXWwpqgQRQdZzZr57eC7mgxA6dy2qNvZ3enfd+Mp T3aA== X-Gm-Message-State: AOJu0Yx/4eI/B+liH0DMs3NqVlKa6/YebHe8SQXYa3Leigp+WY4NH7rf CrGkuzuiPyEHTdMcH0WgtfNqaZ0yk4FGdBRUs8YggDzI8Q2CJxYvLcRY5Q== X-Gm-Gg: ASbGncu4OS2YXDZ5Amvo3pweD2eSMC1y0bZwWwLKGDJJ2dv9IfOyWee5WyKxKjXNK+D vSKWbis+gzOJo7CkvybWoS2h/ajQSYeGnUP2epPogzLgvpgrwMBUtx669JSonyaSgHPSY1t45uy jHPrLVdBdRjogy5M70AysN5+oy5bfSVEiPBd1os04twkqx2cEpvj/DZ4Nbjm0N3ALIVz9knqMRE vhm6T+gH5l6eAY9g6j6wjYT+hi1kNx5Tv2EekDKNxuOe2+bumJp1c8BSziphHOfRxtUXWYX0Pqz HrJynPvz0Opg5rNVxGao9yzFkBDbdv9UQFIszA4LQM2iFdIOst1ZkKh6udU= X-Google-Smtp-Source: AGHT+IHMgLbVEXiJB34VCCiXCipf0crdYVcL1JhoR1KyRThEj1d3OR+u3HUkpNWA5MyPJN+S5Ed+2Q== X-Received: by 2002:a17:90b:2e44:b0:306:b65e:13a8 with SMTP id 98e67ed59e1d1-30823633590mr10098884a91.8.1744470724041; Sat, 12 Apr 2025 08:12:04 -0700 (PDT) Received: from [127.0.0.1] (master.gitmailbox.com. [34.83.118.50]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-3082280bb79sm4022206a91.16.2025.04.12.08.12.03 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Sat, 12 Apr 2025 08:12:03 -0700 (PDT) Message-Id: <pull.64.ffstaging.FFmpeg.1744470718.ffmpegagent@gmail.com> From: ffmpegagent <ffmpegagent@gmail.com> Date: Sat, 12 Apr 2025 15:11:55 +0000 Fcc: Sent MIME-Version: 1.0 To: ffmpeg-devel@ffmpeg.org Subject: [FFmpeg-devel] [PATCH 0/3] avutil/dict2: Add AVDictionary2 with hash-based lookup X-BeenThere: ffmpeg-devel@ffmpeg.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: FFmpeg development discussions and patches <ffmpeg-devel.ffmpeg.org> List-Unsubscribe: <https://ffmpeg.org/mailman/options/ffmpeg-devel>, <mailto:ffmpeg-devel-request@ffmpeg.org?subject=unsubscribe> List-Archive: <https://ffmpeg.org/pipermail/ffmpeg-devel> List-Post: <mailto:ffmpeg-devel@ffmpeg.org> List-Help: <mailto:ffmpeg-devel-request@ffmpeg.org?subject=help> List-Subscribe: <https://ffmpeg.org/mailman/listinfo/ffmpeg-devel>, <mailto:ffmpeg-devel-request@ffmpeg.org?subject=subscribe> Reply-To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org> Cc: softworkz <softworkz@hotmail.com> Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" <ffmpeg-devel-bounces@ffmpeg.org> Archived-At: <https://master.gitmailbox.com/ffmpegdev/pull.64.ffstaging.FFmpeg.1744470718.ffmpegagent@gmail.com/> List-Archive: <https://master.gitmailbox.com/ffmpegdev/> List-Post: <mailto:ffmpegdev@gitmailbox.com> This is probably a PREMIERE. This whole patchset has been antirely authored by AI, wich means that I haven't written a single line of code. Still it had required a lot of strong guidance, so it wouldn't have been able to do it alone. Even though it was an experiment, it is still meant to be a serious submission - otherwisse it would be a pointless endeavour. The instructions were actuall given by Michael through his recent RFC message and I hat assembled them from two of the e-mails to this: https://gist.github.com/softworkz/c7a60c49e9e2b087bdf276ddf5dcf843 The initial direction was closely along the proposed text and atttempting to use avtree for the search, but it struggled hard on that (one issue was about translating/adapting the callback-based tree-enumeration to an iterator-based API without doing allocations (which I forbid). It ended up genereating a hash-based dictionary and after rejecting it for 2h, I let it go with it - also due to the great performacne profile that it provides. The original approach had implemented the single-memory strategy as proposed by Michael but it hasn't been done for the final implementation (in this PR). From the figures it just doesn't appear to be worth the effort. When you have achieved an improvement by like factor 100 - which is HUGE - then there's not much point in spending effort on something which woiuld bring an improvement by a single percent at best. Anyway, it can still be improved. This PR provides a solid hash-based dictionary without over-complication and decent performance - at least when comparing to the old dictionary, The only cases where AVDictionary is preferable over AVDictionary2 is when there's a small number iof itemss in the dictionary or parameters like NO_STRDUP are used. softworkz (3): avutil/dict2: Add AVDictionary2 with hash-based lookup doc/dict2: Add doc and api change for AVDictionary2 tests/dict2: Add tests and benchmark for AVDictionary2 doc/APIchanges | 3 + doc/dict2.md | 44 +++++ libavutil/Makefile | 3 + libavutil/dict2.c | 335 +++++++++++++++++++++++++++++++++++++ libavutil/dict2.h | 167 ++++++++++++++++++ libavutil/tests/dict2.c | 185 ++++++++++++++++++++ libavutil/version.h | 2 +- tests/api/Makefile | 1 + tests/api/api-dict2-test.c | 122 ++++++++++++++ tests/fate/api.mak | 15 ++ tools/Makefile | 2 +- tools/dict2_benchmark.c | 237 ++++++++++++++++++++++++++ 12 files changed, 1114 insertions(+), 2 deletions(-) create mode 100644 doc/dict2.md create mode 100644 libavutil/dict2.c create mode 100644 libavutil/dict2.h create mode 100644 libavutil/tests/dict2.c create mode 100644 tests/api/api-dict2-test.c create mode 100644 tools/dict2_benchmark.c base-commit: b02985b12c30fe44ca5abf5f90c39f2542b10ad7 Published-As: https://github.com/ffstaging/FFmpeg/releases/tag/pr-ffstaging-64%2Fsoftworkz%2Favdict2_test-v1 Fetch-It-Via: git fetch https://github.com/ffstaging/FFmpeg pr-ffstaging-64/softworkz/avdict2_test-v1 Pull-Request: https://github.com/ffstaging/FFmpeg/pull/64 -- ffmpeg-codebot _______________________________________________ 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".