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 5392C4CFC8
for <ffmpegdev@gitmailbox.com>; Tue, 15 Apr 2025 20:36:56 +0000 (UTC)
Received: from [127.0.1.1] (localhost [127.0.0.1])
by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id DED03687D40;
Tue, 15 Apr 2025 23:36:51 +0300 (EEST)
Received: from relay8-d.mail.gandi.net (relay8-d.mail.gandi.net
[217.70.183.201])
by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id EFD45687A49
for <ffmpeg-devel@ffmpeg.org>; Tue, 15 Apr 2025 23:36:44 +0300 (EEST)
Received: by mail.gandi.net (Postfix) with ESMTPSA id 4D26543B00
for <ffmpeg-devel@ffmpeg.org>; Tue, 15 Apr 2025 20:36:44 +0000 (UTC)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=niedermayer.cc;
s=gm1; t=1744749404;
h=from:from:reply-to:subject:subject:date:date:message-id:message-id:
to:to:cc:mime-version:mime-version:content-type:content-type:
in-reply-to:in-reply-to:references:references;
bh=ySYleCd232pjyXlB//+gaxiY63zyKfzRG35LiEkBHFg=;
b=RLPem3V7eZ695UuvcUAlYCXttSKNulD0rrdmyk21UTcull9qsPfScycw42iRhiMLjmXesm
n5IDmcxnP2KUVB0yEVn1FSIHF044x8E2PvnyOT5/WnF+0BdWOCqOUGmEoIblW5P7M3GvAV
kGi41B6SLCujTh7RLTCIRFit3XQE/3P/H/bRMyYeJDGQfqKtD+/CV25sixyFAyn9EKCikZ
wjBlhTMLiE/e7gSGskjKfzviBDt13uVWKOpv/M+ZK92V/tFw9QEyCLtq+QYsehcey+U/g3
VorQ+xHAaTIrS+sqvVC3vFwyaQpolh2PU4ihetrNswlfCqOJMcu1edTtuFfOIg==
Date: Tue, 15 Apr 2025 22:36:43 +0200
From: Michael Niedermayer <michael@niedermayer.cc>
To: FFmpeg development discussions and patches <ffmpeg-devel@ffmpeg.org>
Message-ID: <20250415203643.GU4991@pb2>
References: <20250414113328.GM4991@pb2>
<BN0P223MB0358D7E3367462AA4EF9B744BAB32@BN0P223MB0358.NAMP223.PROD.OUTLOOK.COM>
<BN0P223MB03581807CBC5FCBC171EC87CBAB32@BN0P223MB0358.NAMP223.PROD.OUTLOOK.COM>
<20250415191133.GT4991@pb2>
MIME-Version: 1.0
In-Reply-To: <20250415191133.GT4991@pb2>
X-GND-State: clean
X-GND-Score: -85
X-GND-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddvvdeggeejucetufdoteggodetrfdotffvucfrrhhofhhilhgvmecuifetpfffkfdpucggtfgfnhhsuhgsshgtrhhisggvnecuuegrihhlohhuthemuceftddunecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenfghrlhcuvffnffculdduhedmnecujfgurhepfffhvffukfhfgggtuggjsehgtderredttddvnecuhfhrohhmpefoihgthhgrvghlucfpihgvuggvrhhmrgihvghruceomhhitghhrggvlhesnhhivgguvghrmhgrhigvrhdrtggtqeenucggtffrrghtthgvrhhnpeeigeektdejudffjefhteegjedtgeettefggedthfejgfevhfetgeekjedtvdfhveenucfkphepgedurdeiiedrieejrdduudefnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehinhgvthepgedurdeiiedrieejrdduudefpdhhvghloheplhhotggrlhhhohhsthdpmhgrihhlfhhrohhmpehmihgthhgrvghlsehnihgvuggvrhhmrgihvghrrdgttgdpnhgspghrtghpthhtohepuddprhgtphhtthhopehffhhmphgvghdquggvvhgvlhesfhhfmhhpvghgrdhorhhg
X-GND-Sasl: michael@niedermayer.cc
Subject: Re: [FFmpeg-devel] AVDictionary vs. AVSet (AVDictionary2
approximation)
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>
Content-Type: multipart/mixed; boundary="===============6401034642465109932=="
Errors-To: ffmpeg-devel-bounces@ffmpeg.org
Sender: "ffmpeg-devel" <ffmpeg-devel-bounces@ffmpeg.org>
Archived-At: <https://master.gitmailbox.com/ffmpegdev/20250415203643.GU4991@pb2/>
List-Archive: <https://master.gitmailbox.com/ffmpegdev/>
List-Post: <mailto:ffmpegdev@gitmailbox.com>
--===============6401034642465109932==
Content-Type: multipart/signed; micalg=pgp-sha512;
protocol="application/pgp-signature"; boundary="mTjdWr6EzgKaNVan"
Content-Disposition: inline
--mTjdWr6EzgKaNVan
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
On Tue, Apr 15, 2025 at 09:11:33PM +0200, Michael Niedermayer wrote:
> On Mon, Apr 14, 2025 at 01:02:00PM +0000, softworkz . wrote:
> >=20
> >=20
> > > -----Original Message-----
> > > From: ffmpeg-devel <ffmpeg-devel-bounces@ffmpeg.org> On Behalf Of
> > > softworkz .
> > > Sent: Montag, 14. April 2025 14:40
> > > To: FFmpeg development discussions and patches <ffmpeg-
> > > devel@ffmpeg.org>
> > > Subject: Re: [FFmpeg-devel] AVDictionary vs. AVSet (AVDictionary2
> > > approximation)
> > >=20
> > >=20
> > >=20
> > > > -----Original Message-----
> > > > From: ffmpeg-devel <ffmpeg-devel-bounces@ffmpeg.org> On Behalf Of
> > > > Michael Niedermayer
> > > > Sent: Montag, 14. April 2025 13:33
> > > > To: FFmpeg development discussions and patches <ffmpeg-
> > > > devel@ffmpeg.org>
> > > > Subject: [FFmpeg-devel] AVDictionary vs. AVSet (AVDictionary2
> > > > approximation)
> > > >
> > > > Hi
> > > >
> > > > I just posted a AVSet implementation i wrote in the last 2 days (yes
> > > > thats
> > > > why i did dissapear for the last 2 days)
> > > >
> > > > My plan was to use that AVSet as basis for AVDictionary2 in case
> > > > benchmarks indicate that its worth it, so is it ?
> > > >
> > > > with 3 entries (100000 runs)
> > > > AVDictionary 0.040sec
> > > > AVSet 0.027sec
> > > >
> > > > with 5 entries (100000 runs)
> > > > AVDictionary 0.065sec
> > > > AVSet 0.042sec
> > > >
> > > > with 10 entries (100000 runs)
> > > > AVDictionary 0.193sec
> > > > AVSet 0.087sec
> > > >
> > > > with 100 entries (100000 runs)
> > > > AVDictionary 8.7 sec
> > > > AVSet 1.4 sec
> > > >
> > > > with 1000 entries (1000 runs)
> > > > AVDictionary 8.0 sec
> > > > AVSet 0.240 sec
> > > >
> > > > with 10000 entries (10 runs)
> > > > AVDictionary 7.2 sec
> > > > AVSet 0.042 sec
> > > >
> > > >
> > > > I was a bit surprised for the 3 and 5 entry case, maybe my benchmark
> > > > is buggy or
> > > > AVSet is, but then AVDictionary is pretty bad with memory
> > > allocations
> > > >
> > > > AVDictionary needs to strdup every key and value, needs to allocate
> > > > the AVDictionary itself and reallocs the entry array each time
> > > > thats 10 memory allocation related calls for adding 3 entries
> > > >
> > > > while AVSet allocates the AVSet and then uses av_fast_realloc() for
> > > > the array
> > > > and theres nothing else, the key/value goes in that array too
> > > >
> > > >
> > > > bechmark code used is below:
> > > >
> > > >
> > > > #if 0
> > > > for (int runs =3D 0; runs < 100000; runs++) {
> > > > AVSet *set =3D av_set_new(strcmp, NULL, NULL);
> > > > for(int pass =3D 0; pass < 2; pass++) {
> > > > unsigned r =3D 5;
> > > > for(int i=3D0; i<100; i++) {
> > > > r =3D r*123 + 7;
> > > > char str[2*7] =3D "TESTXXTESTXX";
> > > > str[4] =3D r;
> > > > str[5] =3D r>>8;
> > > > if(pass =3D=3D 0) {
> > > > av_set_add(set, str, 2*7, 0);
> > > > } else {
> > > > av_set_get(set, NULL, str, NULL);
> > > > }
> > > > }
> > > > }
> > > > av_set_free(&set);
> > > > }
> > > > #else
> > > > for (int runs =3D 0; runs < 100000; runs++) {
> > > > AVDictionary *dict =3D NULL;
> > > > for(int pass =3D 0; pass < 2; pass++) {
> > > > unsigned r =3D 5;
> > > > for(int i=3D0; i<100; i++) {
> > > > r =3D r*123 + 7;
> > > > char str[7] =3D "TEST";
> > > > str[4] =3D r;
> > > > str[5] =3D r>>8;
> > > > if(pass =3D=3D 0) {
> > > > av_dict_set(&dict, str, str, 0);
> > > > } else {
> > > > av_dict_get(dict, str, NULL, 0);
> > > > }
> > > > }
> > > > }
> > > > av_dict_free(&dict);
> > > > }
> > > > #endif
> > > >
> > > >
> > > > --
> > >=20
> > > Hi Michael,
> > >=20
> > >=20
> > > what's not quite realistic is that all keys are starting with the same
> > > 4 characters. This affects the lookups of course - and probably
> > > (maybe) not equally for both sides.
> > >=20
> > > Doesn't the code create duplicate keys (at least when it gets > 65536
> > > it will for sure) ?
> > >=20
> > > So, I think, the keys should be completely random (all chars).
> > >=20
> > > I would also check whether the lookups are successful (just to be
> > > sure).
> >=20
> > Sorry, I forgot the most important one:=20
> >=20
> > Timing for population and lookup should be measured separately..
>=20
> Sure, for the v2 (AVMap) i just posted
>=20
> with TESTXX / TESTXX strings where XX is random
>=20
> 1000 entries
> 5354505 decicycles in av_map_add, 512 runs, 0 skips
> 4040575 decicycles in av_map_get, 512 runs, 0 skips
> 148082828 decicycles in av_dict_set, 512 runs, 0 skips
> 145828939 decicycles in av_dict_get, 512 runs, 0 skips
>=20
> 100 entries
> 332015 decicycles in av_map_add, 512 runs, 0 skips
> 193726 decicycles in av_map_get, 512 runs, 0 skips
> 1697242 decicycles in av_dict_set, 512 runs, 0 skips
> 1392837 decicycles in av_dict_get, 512 runs, 0 skips
>=20
> 10 entries
> 21142 decicycles in av_map_add, 512 runs, 0 skips
> 11395 decicycles in av_map_get, 512 runs, 0 skips
> 45663 decicycles in av_dict_set, 512 runs, 0 skips
> 19756 decicycles in av_dict_get, 512 runs, 0 skips
>=20
> 5 entries
> 9210 decicycles in av_map_add, 512 runs, 0 skips
> 4870 decicycles in av_map_get, 511 runs, 1 skips
> 18823 decicycles in av_dict_set, 512 runs, 0 skips
> 5483 decicycles in av_dict_get, 512 runs, 0 skips
>=20
> 3 entries
> 5693 decicycles in av_map_add, 512 runs, 0 skips
> 2645 decicycles in av_map_get, 512 runs, 0 skips
> 11462 decicycles in av_dict_set, 511 runs, 1 skips
> 2532 decicycles in av_dict_get, 512 runs, 0 skips
>=20
>=20
>=20
> with XXST / XXST strings where XX is random
>=20
> 1000 entries
> 5321153 decicycles in av_map_add, 512 runs, 0 skips
> 4295153 decicycles in av_map_get, 512 runs, 0 skips
> 70417784 decicycles in av_dict_set, 512 runs, 0 skips
> 68188612 decicycles in av_dict_get, 512 runs, 0 skips
>=20
> 100 entries
> 322872 decicycles in av_map_add, 512 runs, 0 skips
> 216032 decicycles in av_map_get, 511 runs, 1 skips
> 1022088 decicycles in av_dict_set, 512 runs, 0 skips
> 723612 decicycles in av_dict_get, 512 runs, 0 skips
>=20
> 10 entries
> 20993 decicycles in av_map_add, 512 runs, 0 skips
> 11744 decicycles in av_map_get, 512 runs, 0 skips
> 38945 decicycles in av_dict_set, 512 runs, 0 skips
> 11308 decicycles in av_dict_get, 512 runs, 0 skips
>=20
> 5 entries
> 10007 decicycles in av_map_add, 511 runs, 1 skips
> 5004 decicycles in av_map_get, 512 runs, 0 skips
> 17374 decicycles in av_dict_set, 511 runs, 1 skips
> 3848 decicycles in av_dict_get, 512 runs, 0 skips
>=20
> 3 entries
> 5896 decicycles in av_map_add, 512 runs, 0 skips
> 2765 decicycles in av_map_get, 512 runs, 0 skips
> 11396 decicycles in av_dict_set, 511 runs, 1 skips
> 2029 decicycles in av_dict_get, 512 runs, 0 skips
This contained a bug, Dictionary used C code written by FFmpeg developers
and did a case insensitive compare while AVMap used strcmp() which
is case sensitive and not written by FFmpeg developers.
I will post new test results with av_strcasecmp() instead
and also put it in a new thread so it can be found easier
thx
[...]
--=20
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
Into a blind darkness they enter who follow after the Ignorance,
they as if into a greater darkness enter who devote themselves
to the Knowledge alone. -- Isha Upanishad
--mTjdWr6EzgKaNVan
Content-Type: application/pgp-signature; name="signature.asc"
-----BEGIN PGP SIGNATURE-----
iF0EABEKAB0WIQSf8hKLFH72cwut8TNhHseHBAsPqwUCZ/7DWAAKCRBhHseHBAsP
q1lrAKCHO8ojARPEGr1zk1OPFhNGYX3HDACeOCJ/sGIhuXbws6aF2IELdl5JRZw=
=tHX7
-----END PGP SIGNATURE-----
--mTjdWr6EzgKaNVan--
--===============6401034642465109932==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
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".
--===============6401034642465109932==--