Topic: Clusters

Author: Sven Bieg <svenbieg@outlook.de>
Date: Fri, 12 Oct 2018 16:01:49 +0000 Raw View 
--_000_DB7PR02MB4140F37CEBA876BD7102E223B1E20DB7PR02MB4140eurp_
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hello Mr. Gustafsson,

in fact my algorithm doesn=E2=80=99t build a binary tree, it builds a pyram=
id, 50 times more steep than the real ones! Have You had a look at my homep=
age? There is a short overview how it works. I=E2=80=99m from Germany, plea=
se excuse my bad english!

Best regards,

Sven Bieg

--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/DB7PR02MB4140F37CEBA876BD7102E223B1E20%40DB7PR02=
MB4140.eurprd02.prod.outlook.com.

--_000_DB7PR02MB4140F37CEBA876BD7102E223B1E20DB7PR02MB4140eurp_
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<html xmlns:o=3D"urn:schemas-microsoft-com:office:office" xmlns:w=3D"urn:sc=
hemas-microsoft-com:office:word" xmlns:m=3D"http://schemas.microsoft.com/of=
fice/2004/12/omml" xmlns=3D"http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv=3D"Content-Type" content=3D"text/html; charset=3DWindows-1=
252">
<meta name=3D"Generator" content=3D"Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
 {font-family:"Cambria Math";
 panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
 {font-family:Calibri;
 panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
 {margin:0cm;
 margin-bottom:.0001pt;
 font-size:11.0pt;
 font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
 {mso-style-priority:99;
 color:blue;
 text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
 {mso-style-priority:99;
 color:#954F72;
 text-decoration:underline;}
..MsoChpDefault
 {mso-style-type:export-only;}
@page WordSection1
 {size:612.0pt 792.0pt;
 margin:70.85pt 70.85pt 2.0cm 70.85pt;}
div.WordSection1
 {page:WordSection1;}
--></style>
</head>
<body lang=3D"DE" link=3D"blue" vlink=3D"#954F72">
<div class=3D"WordSection1">
<p class=3D"MsoNormal">Hello Mr. Gustafsson,</p>
<p class=3D"MsoNormal"><o:p>&nbsp;</o:p></p>
<p class=3D"MsoNormal">in fact my algorithm doesn=E2=80=99t build a binary =
tree, it builds a pyramid, 50 times more steep than the real ones! Have You=
 had a look at my homepage? There is a short overview how it works. I=E2=80=
=99m from Germany, please excuse my bad english!</p>
<p class=3D"MsoNormal"><o:p>&nbsp;</o:p></p>
<p class=3D"MsoNormal">Best regards,</p>
<p class=3D"MsoNormal"><o:p>&nbsp;</o:p></p>
<p class=3D"MsoNormal">Sven Bieg</p>
<p class=3D"MsoNormal"><o:p>&nbsp;</o:p></p>
</div>
</body>
</html>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/DB7PR02MB4140F37CEBA876BD7102E223B1E2=
0%40DB7PR02MB4140.eurprd02.prod.outlook.com?utm_medium=3Demail&utm_source=
=3Dfooter">https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/DB7=
PR02MB4140F37CEBA876BD7102E223B1E20%40DB7PR02MB4140.eurprd02.prod.outlook.c=
om</a>.<br />

--_000_DB7PR02MB4140F37CEBA876BD7102E223B1E20DB7PR02MB4140eurp_--

.

Author: Magnus Fromreide <magfr@lysator.liu.se>
Date: Fri, 12 Oct 2018 23:31:15 +0200 Raw View 
On Fri, Oct 12, 2018 at 04:01:49PM +0000, Sven Bieg wrote:
> Hello Mr. Gustafsson,
>=20
> in fact my algorithm doesn=E2=80=99t build a binary tree, it builds a pyr=
amid, 50 times more steep than the real ones! Have You had a look at my hom=
epage? There is a short overview how it works. I=E2=80=99m from Germany, pl=
ease excuse my bad english!

He said B-tree, not binary tree. They are very different beasts.

See e.g. wikipedia: https://en.wikipedia.org/wiki/B-tree

/MF

> Best regards,
>=20
> Sven Bieg
>=20
> --=20
> You received this message because you are subscribed to the Google Groups=
 "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an=
 email to std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> To view this discussion on the web visit https://groups.google.com/a/isoc=
pp.org/d/msgid/std-proposals/DB7PR02MB4140F37CEBA876BD7102E223B1E20%40DB7PR=
02MB4140.eurprd02.prod.outlook.com.

--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/20181012213114.GA23377%40noemi.

.

Author: Sven Bieg <svenbieg@outlook.de>
Date: Sat, 13 Oct 2018 07:12:12 +0000 Raw View 
--_000_DB7PR02MB4140920851E6E3B1DF449453B1E30DB7PR02MB4140eurp_
Content-Type: text/plain; charset="UTF-8"

I've done a comparison to std::list and std::map. You can find some diagrams at

http://svenbieg.azurewebsites.net/Clusters/List


and

http://svenbieg.azurewebsites.net/Clusters/Index


I don't know if Microsoft has it's own Implementation, but i get much better results using Clusters!

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/DB7PR02MB4140920851E6E3B1DF449453B1E30%40DB7PR02MB4140.eurprd02.prod.outlook.com.

--_000_DB7PR02MB4140920851E6E3B1DF449453B1E30DB7PR02MB4140eurp_
Content-Type: text/html; charset="UTF-8"
Content-ID: <27D41A5EE7105642BD8FF4F5264CB7DD@sct-15-20-755-16-msonline-outlook-c162d.templateTenant>
Content-Transfer-Encoding: quoted-printable

<html>
<head>
<meta http-equiv=3D"Content-Type" content=3D"text/html; charset=3Dutf-8">
</head>
<body>
<p dir=3D"ltr" style=3D"margin-top:0; margin-bottom:0;">I've done a compari=
son to std::list and std::map. You can find some diagrams at</p>
<p dir=3D"ltr" style=3D"margin-top:0; margin-bottom:0;">http://svenbieg.azu=
rewebsites.net/Clusters/List</p>
<br>
<p dir=3D"ltr" style=3D"margin-top:0; margin-bottom:0;">and</p>
<p dir=3D"ltr" style=3D"margin-top:0; margin-bottom:0;">http://svenbieg.azu=
rewebsites.net/Clusters/Index</p>
<br>
<p dir=3D"ltr" style=3D"margin-top:0; margin-bottom:0;">I don't know if Mic=
rosoft has it's own Implementation, but i get much better results using Clu=
sters!</p>
<br>
</body>
</html>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/DB7PR02MB4140920851E6E3B1DF449453B1E3=
0%40DB7PR02MB4140.eurprd02.prod.outlook.com?utm_medium=3Demail&utm_source=
=3Dfooter">https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/DB7=
PR02MB4140920851E6E3B1DF449453B1E30%40DB7PR02MB4140.eurprd02.prod.outlook.c=
om</a>.<br />

--_000_DB7PR02MB4140920851E6E3B1DF449453B1E30DB7PR02MB4140eurp_--

.

Author: pasa@lib.hu
Date: Sun, 28 Oct 2018 03:34:18 -0700 (PDT) Raw View 
------=_Part_1087_304986856.1540722858792
Content-Type: multipart/alternative;
 boundary="----=_Part_1088_1239039843.1540722858792"

------=_Part_1088_1239039843.1540722858792
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

I just noticed this and the other tests. They all add numbers in a strict=
=20
increasing order. This may create a serious skew in the test results. In=20
any potential direction, but my estimate is that your algo takes a serious=
=20
benefit from that, ike as if you tested a vector.insert() only adding to=20
the end instead of anywhere in the middle.

Run the test with different patterns, like full backwards, some number=20
mappings (i.e odd(x) ? -x : x ). And random numbers for tests it is=20
possible.

You also need to provide the compiler version and flags used in the run.

2018. okt=C3=B3ber 13., szombat 9:12:16 UTC+2 id=C5=91pontban Sven Bieg a k=
=C3=B6vetkez=C5=91t=20
=C3=ADrta:
>
> I've done a comparison to std::list and std::map. You can find some=20
> diagrams at
>
> http://svenbieg.azurewebsites.net/Clusters/List
>
> and
>
> http://svenbieg.azurewebsites.net/Clusters/Index
>
> I don't know if Microsoft has it's own Implementation, but i get much=20
> better results using Clusters!
>
>

--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/4b5a3f01-c9be-436c-835c-3024a406fb47%40isocpp.or=
g.

------=_Part_1088_1239039843.1540722858792
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>I just noticed this and the other tests. They all add=
 numbers in a strict increasing order. This may create a serious skew in th=
e test results. In any potential direction, but my estimate is that your al=
go takes a serious benefit from that, ike as if you tested a vector.insert(=
) only adding to the end instead of anywhere in the middle.</div><div><br><=
/div><div>Run the test with different patterns, like full backwards, some n=
umber mappings (i.e odd(x) ? -x : x ). And random numbers for tests it is p=
ossible.</div><div><br></div><div>You also need to provide the compiler ver=
sion and flags used in the run.<br></div><br>2018. okt=C3=B3ber 13., szomba=
t 9:12:16 UTC+2 id=C5=91pontban Sven Bieg a k=C3=B6vetkez=C5=91t =C3=ADrta:=
<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;bor=
der-left: 1px #ccc solid;padding-left: 1ex;">



<div>
<p dir=3D"ltr" style=3D"margin-top:0;margin-bottom:0">I&#39;ve done a compa=
rison to std::list and std::map. You can find some diagrams at</p>
<p dir=3D"ltr" style=3D"margin-top:0;margin-bottom:0"><a href=3D"http://sve=
nbieg.azurewebsites.net/Clusters/List" target=3D"_blank" rel=3D"nofollow" o=
nmousedown=3D"this.href=3D&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2F=
svenbieg.azurewebsites.net%2FClusters%2FList\x26sa\x3dD\x26sntz\x3d1\x26usg=
\x3dAFQjCNHFr31KjEDtZxcD9kVHzAAjya_tjA&#39;;return true;" onclick=3D"this.h=
ref=3D&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fsvenbieg.azurewebsit=
es.net%2FClusters%2FList\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNHFr31KjEDt=
ZxcD9kVHzAAjya_tjA&#39;;return true;">http://svenbieg.azurewebsites.<wbr>ne=
t/Clusters/List</a></p>
<br>
<p dir=3D"ltr" style=3D"margin-top:0;margin-bottom:0">and</p>
<p dir=3D"ltr" style=3D"margin-top:0;margin-bottom:0"><a href=3D"http://sve=
nbieg.azurewebsites.net/Clusters/Index" target=3D"_blank" rel=3D"nofollow" =
onmousedown=3D"this.href=3D&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2=
Fsvenbieg.azurewebsites.net%2FClusters%2FIndex\x26sa\x3dD\x26sntz\x3d1\x26u=
sg\x3dAFQjCNHc1x99qjiQBERfVovEg6lxc1Yznw&#39;;return true;" onclick=3D"this=
..href=3D&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fsvenbieg.azurewebs=
ites.net%2FClusters%2FIndex\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNHc1x99q=
jiQBERfVovEg6lxc1Yznw&#39;;return true;">http://svenbieg.azurewebsites.<wbr=
>net/Clusters/Index</a></p>
<br>
<p dir=3D"ltr" style=3D"margin-top:0;margin-bottom:0">I don&#39;t know if M=
icrosoft has it&#39;s own Implementation, but i get much better results usi=
ng Clusters!</p>
<br>
</div>

</blockquote></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/4b5a3f01-c9be-436c-835c-3024a406fb47%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/4b5a3f01-c9be-436c-835c-3024a406fb47=
%40isocpp.org</a>.<br />

------=_Part_1088_1239039843.1540722858792--

------=_Part_1087_304986856.1540722858792--

.

Author: pasa@lib.hu
Date: Sun, 28 Oct 2018 04:12:54 -0700 (PDT) Raw View 
------=_Part_1263_673909425.1540725174684
Content-Type: multipart/alternative;
 boundary="----=_Part_1264_551946710.1540725174684"

------=_Part_1264_551946710.1540725174684
Content-Type: text/plain; charset="UTF-8"

Also for the memory footprint tests use a series of Ts with different
sizeof. As the nodes have fixed overhead (like 3 pointers in map), the
waste will show different ratio as the type gets fatter, not the minimal
that is used in the examples.

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/f00f3643-091f-47d0-bb88-5f187109f6d3%40isocpp.org.

------=_Part_1264_551946710.1540725174684
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Also for the memory footprint tests use a series of Ts wit=
h different sizeof. As the nodes have fixed overhead (like 3 pointers in ma=
p), the waste will show different ratio as the type gets fatter, not the mi=
nimal that is used in the examples.<br></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/f00f3643-091f-47d0-bb88-5f187109f6d3%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/f00f3643-091f-47d0-bb88-5f187109f6d3=
%40isocpp.org</a>.<br />

------=_Part_1264_551946710.1540725174684--

------=_Part_1263_673909425.1540725174684--

.

Author: svenbieg@web.de
Date: Sun, 28 Oct 2018 06:04:18 -0700 (PDT) Raw View 
------=_Part_1103_1230453981.1540731858950
Content-Type: multipart/alternative;
 boundary="----=_Part_1104_24974358.1540731858950"

------=_Part_1104_24974358.1540731858950
Content-Type: text/plain; charset="UTF-8"

Hello Mr. Pasa,

You are right. I don't know how the map works internally, but i know about
clusters.
In a clusters, the worst case is push_front(), then the maximum number of
items
has to be moved. I'm going to add this test as worst case scenario to the
specification.

The groups in a cluster at half-full at minimum, except there is only one
group.
This means there is an overhead of about 100% at maximum.
The overhead for parent-groups is about 100 pointers per 10.000 items.
With a minimal item-size of 1 byte, this would be another 4%.
The maximum overhead is then 104%, wich is less than in the map-class.

Best regards,

Sven

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/3a768ae7-efa1-4b64-8e3b-2c66fd598ad0%40isocpp.org.

------=_Part_1104_24974358.1540731858950
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>Hello Mr. Pasa,</div><div><br></div><div>You are righ=
t. I don&#39;t know how the map works internally, but i know about clusters=
..</div><div>In a clusters, the worst case is push_front(), then the maximum=
 number of items</div><div>has to be moved. I&#39;m going to add this test =
as worst case scenario to the specification.</div><div><br></div><div>The g=
roups in a cluster at half-full at minimum, except there is only one group.=
</div><div>This means there is an overhead of about 100% at maximum.</div><=
div>The overhead for parent-groups is about 100 pointers per 10.000 items.<=
/div><div>With a minimal item-size of 1 byte, this would be another 4%.</di=
v><div>The maximum overhead is then 104%, wich is less than in the map-clas=
s.</div><div><br></div><div>Best regards,</div><div><br></div><div>Sven</di=
v></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/3a768ae7-efa1-4b64-8e3b-2c66fd598ad0%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/3a768ae7-efa1-4b64-8e3b-2c66fd598ad0=
%40isocpp.org</a>.<br />

------=_Part_1104_24974358.1540731858950--

------=_Part_1103_1230453981.1540731858950--

.

Author: svenbieg@web.de
Date: Sun, 28 Oct 2018 06:14:08 -0700 (PDT) Raw View 
------=_Part_1290_1197905954.1540732448267
Content-Type: multipart/alternative;
 boundary="----=_Part_1291_538400092.1540732448267"

------=_Part_1291_538400092.1540732448267
Content-Type: text/plain; charset="UTF-8"

Hello Mr. Pasa,

You are right. I don't know how the map works internally, but i know about
clusters.
In a clusters, the worst case is push_front(), then the maximum number of
items
has to be moved. I'm going to add this test as worst case scenario to the
specification.

The groups in a cluster are half-full at minimum, except there is only one
group.
This means there is an overhead of about 100% at maximum.
The overhead for parent-groups is about 100 pointers per 10.000 items.
With a minimal item-size of 1 byte, this would be another 4%.
The maximum overhead is then 104%.
With an item-size less the size of 3 pointers, the cluster can also save
memory.

Best regards,
Sven


--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/51cf2db1-b868-4404-b9e1-fabb37491c8a%40isocpp.org.

------=_Part_1291_538400092.1540732448267
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"F0XO1GC-ed-a" style=3D"margin: 0px 0px 0px 4=
4px; padding: 0px 0px 0px 5px; border: 0px rgb(34, 34, 34); border-image: n=
one; text-align: left; color: rgb(34, 34, 34); text-transform: none; text-i=
ndent: 0px; letter-spacing: normal; font-size: 13px; font-variant: normal; =
word-spacing: 0px; white-space: normal; orphans: 2; -webkit-text-stroke-wid=
th: 0px; background-color: transparent;"><div tabindex=3D"0" class=3D"F0XO1=
GC-nb-P" style=3D"border-bottom-color: rgb(34, 34, 34); border-bottom-style=
: none; border-bottom-width: 0px; border-image-outset: 0; border-image-repe=
at: stretch; border-image-slice: 100%; border-image-source: none; border-im=
age-width: 1; border-left-color: rgb(34, 34, 34); border-left-style: none; =
border-left-width: 0px; border-right-color: rgb(34, 34, 34); border-right-s=
tyle: none; border-right-width: 0px; border-top-color: rgb(34, 34, 34); bor=
der-top-style: none; border-top-width: 0px; color: rgb(34, 34, 34); line-he=
ight: normal; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; marg=
in-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; pa=
dding-top: 0px;"><div style=3D"border-bottom-color: rgb(34, 34, 34); border=
-bottom-style: none; border-bottom-width: 0px; border-image-outset: 0; bord=
er-image-repeat: stretch; border-image-slice: 100%; border-image-source: no=
ne; border-image-width: 1; border-left-color: rgb(34, 34, 34); border-left-=
style: none; border-left-width: 0px; border-right-color: rgb(34, 34, 34); b=
order-right-style: none; border-right-width: 0px; border-top-color: rgb(34,=
 34, 34); border-top-style: none; border-top-width: 0px; margin-bottom: 0px=
; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px=
; padding-left: 0px; padding-right: 0px; padding-top: 0px;"><div style=3D"b=
order-bottom-color: rgb(34, 34, 34); border-bottom-style: none; border-bott=
om-width: 0px; border-image-outset: 0; border-image-repeat: stretch; border=
-image-slice: 100%; border-image-source: none; border-image-width: 1; borde=
r-left-color: rgb(34, 34, 34); border-left-style: none; border-left-width: =
0px; border-right-color: rgb(34, 34, 34); border-right-style: none; border-=
right-width: 0px; border-top-color: rgb(34, 34, 34); border-top-style: none=
; border-top-width: 0px; margin-bottom: 0px; margin-left: 0px; margin-right=
: 0px; margin-top: 0px; overflow: auto; padding-bottom: 0px; padding-left: =
0px; padding-right: 0px; padding-top: 0px;"><div style=3D"border-bottom-col=
or: rgb(34, 34, 34); border-bottom-style: none; border-bottom-width: 0px; b=
order-image-outset: 0; border-image-repeat: stretch; border-image-slice: 10=
0%; border-image-source: none; border-image-width: 1; border-left-color: rg=
b(34, 34, 34); border-left-style: none; border-left-width: 0px; border-righ=
t-color: rgb(34, 34, 34); border-right-style: none; border-right-width: 0px=
; border-top-color: rgb(34, 34, 34); border-top-style: none; border-top-wid=
th: 0px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-to=
p: 0px; max-height: 10000px; padding-bottom: 0px; padding-left: 0px; paddin=
g-right: 0px; padding-top: 0px;"><div style=3D"border-bottom-color: rgb(34,=
 34, 34); border-bottom-style: none; border-bottom-width: 0px; border-image=
-outset: 0; border-image-repeat: stretch; border-image-slice: 100%; border-=
image-source: none; border-image-width: 1; border-left-color: rgb(34, 34, 3=
4); border-left-style: none; border-left-width: 0px; border-right-color: rg=
b(34, 34, 34); border-right-style: none; border-right-width: 0px; border-to=
p-color: rgb(34, 34, 34); border-top-style: none; border-top-width: 0px; ma=
rgin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; pad=
ding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px;"=
 dir=3D"ltr"><div style=3D"border-bottom-color: rgb(34, 34, 34); border-bot=
tom-style: none; border-bottom-width: 0px; border-image-outset: 0; border-i=
mage-repeat: stretch; border-image-slice: 100%; border-image-source: none; =
border-image-width: 1; border-left-color: rgb(34, 34, 34); border-left-styl=
e: none; border-left-width: 0px; border-right-color: rgb(34, 34, 34); borde=
r-right-style: none; border-right-width: 0px; border-top-color: rgb(34, 34,=
 34); border-top-style: none; border-top-width: 0px; margin-bottom: 0px; ma=
rgin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; pa=
dding-left: 0px; padding-right: 0px; padding-top: 0px;"><div class=3D"F0XO1=
GC-ed-a" style=3D"margin: 0px 0px 0px 44px; padding: 0px 0px 0px 5px; borde=
r: 0px rgb(34, 34, 34); border-image: none; text-align: left; color: rgb(34=
, 34, 34); text-transform: none; text-indent: 0px; letter-spacing: normal; =
font-size: 13px; font-variant: normal; word-spacing: 0px; white-space: norm=
al; orphans: 2; -webkit-text-stroke-width: 0px; background-color: transpare=
nt;"><div tabindex=3D"0" class=3D"F0XO1GC-nb-P" style=3D"border-bottom-colo=
r: rgb(34, 34, 34); border-bottom-style: none; border-bottom-width: 0px; bo=
rder-image-outset: 0; border-image-repeat: stretch; border-image-slice: 100=
%; border-image-source: none; border-image-width: 1; border-left-color: rgb=
(34, 34, 34); border-left-style: none; border-left-width: 0px; border-right=
-color: rgb(34, 34, 34); border-right-style: none; border-right-width: 0px;=
 border-top-color: rgb(34, 34, 34); border-top-style: none; border-top-widt=
h: 0px; color: rgb(34, 34, 34); line-height: normal; margin-bottom: 0px; ma=
rgin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; pa=
dding-left: 0px; padding-right: 0px; padding-top: 0px;"><div style=3D"borde=
r-bottom-color: rgb(34, 34, 34); border-bottom-style: none; border-bottom-w=
idth: 0px; border-image-outset: 0; border-image-repeat: stretch; border-ima=
ge-slice: 100%; border-image-source: none; border-image-width: 1; border-le=
ft-color: rgb(34, 34, 34); border-left-style: none; border-left-width: 0px;=
 border-right-color: rgb(34, 34, 34); border-right-style: none; border-righ=
t-width: 0px; border-top-color: rgb(34, 34, 34); border-top-style: none; bo=
rder-top-width: 0px; margin-bottom: 0px; margin-left: 0px; margin-right: 0p=
x; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: =
0px; padding-top: 0px;"><div style=3D"border-bottom-color: rgb(34, 34, 34);=
 border-bottom-style: none; border-bottom-width: 0px; border-image-outset: =
0; border-image-repeat: stretch; border-image-slice: 100%; border-image-sou=
rce: none; border-image-width: 1; border-left-color: rgb(34, 34, 34); borde=
r-left-style: none; border-left-width: 0px; border-right-color: rgb(34, 34,=
 34); border-right-style: none; border-right-width: 0px; border-top-color: =
rgb(34, 34, 34); border-top-style: none; border-top-width: 0px; margin-bott=
om: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow: au=
to; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top=
: 0px;"><div style=3D"border-bottom-color: rgb(34, 34, 34); border-bottom-s=
tyle: none; border-bottom-width: 0px; border-image-outset: 0; border-image-=
repeat: stretch; border-image-slice: 100%; border-image-source: none; borde=
r-image-width: 1; border-left-color: rgb(34, 34, 34); border-left-style: no=
ne; border-left-width: 0px; border-right-color: rgb(34, 34, 34); border-rig=
ht-style: none; border-right-width: 0px; border-top-color: rgb(34, 34, 34);=
 border-top-style: none; border-top-width: 0px; margin-bottom: 0px; margin-=
left: 0px; margin-right: 0px; margin-top: 0px; max-height: 10000px; padding=
-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px;"><di=
v style=3D"border-bottom-color: rgb(34, 34, 34); border-bottom-style: none;=
 border-bottom-width: 0px; border-image-outset: 0; border-image-repeat: str=
etch; border-image-slice: 100%; border-image-source: none; border-image-wid=
th: 1; border-left-color: rgb(34, 34, 34); border-left-style: none; border-=
left-width: 0px; border-right-color: rgb(34, 34, 34); border-right-style: n=
one; border-right-width: 0px; border-top-color: rgb(34, 34, 34); border-top=
-style: none; border-top-width: 0px; margin-bottom: 0px; margin-left: 0px; =
margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px;=
 padding-right: 0px; padding-top: 0px;" dir=3D"ltr"><div style=3D"border-bo=
ttom-color: rgb(34, 34, 34); border-bottom-style: none; border-bottom-width=
: 0px; border-image-outset: 0; border-image-repeat: stretch; border-image-s=
lice: 100%; border-image-source: none; border-image-width: 1; border-left-c=
olor: rgb(34, 34, 34); border-left-style: none; border-left-width: 0px; bor=
der-right-color: rgb(34, 34, 34); border-right-style: none; border-right-wi=
dth: 0px; border-top-color: rgb(34, 34, 34); border-top-style: none; border=
-top-width: 0px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; m=
argin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px;=
 padding-top: 0px;"><div class=3D"F0XO1GC-ed-a" style=3D"background-color: =
transparent; border-bottom-color: rgb(34, 34, 34); border-bottom-style: non=
e; border-bottom-width: 0px; border-image-outset: 0; border-image-repeat: s=
tretch; border-image-slice: 100%; border-image-source: none; border-image-w=
idth: 1; border-left-color: rgb(34, 34, 34); border-left-style: none; borde=
r-left-width: 0px; border-right-color: rgb(34, 34, 34); border-right-style:=
 none; border-right-width: 0px; border-top-color: rgb(34, 34, 34); border-t=
op-style: none; border-top-width: 0px; color: rgb(34, 34, 34); font-family:=
 &amp;quot;Arial&amp;quot;,&amp;quot;Helvetica&amp;quot;,sans-serif; font-s=
ize: 13px; font-style: normal; font-variant: normal; font-weight: 400; lett=
er-spacing: normal; margin-bottom: 0px; margin-left: 44px; margin-right: 0p=
x; margin-top: 0px; orphans: 2; padding-bottom: 0px; padding-left: 5px; pad=
ding-right: 0px; padding-top: 0px; text-align: left; text-decoration: none;=
 text-indent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; wh=
ite-space: normal; word-spacing: 0px;"><div tabindex=3D"0" class=3D"F0XO1GC=
-nb-P" style=3D"border-bottom-color: rgb(34, 34, 34); border-bottom-style: =
none; border-bottom-width: 0px; border-image-outset: 0; border-image-repeat=
: stretch; border-image-slice: 100%; border-image-source: none; border-imag=
e-width: 1; border-left-color: rgb(34, 34, 34); border-left-style: none; bo=
rder-left-width: 0px; border-right-color: rgb(34, 34, 34); border-right-sty=
le: none; border-right-width: 0px; border-top-color: rgb(34, 34, 34); borde=
r-top-style: none; border-top-width: 0px; color: rgb(34, 34, 34); line-heig=
ht: normal; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin=
-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padd=
ing-top: 0px;"><div style=3D"border-bottom-color: rgb(34, 34, 34); border-b=
ottom-style: none; border-bottom-width: 0px; border-image-outset: 0; border=
-image-repeat: stretch; border-image-slice: 100%; border-image-source: none=
; border-image-width: 1; border-left-color: rgb(34, 34, 34); border-left-st=
yle: none; border-left-width: 0px; border-right-color: rgb(34, 34, 34); bor=
der-right-style: none; border-right-width: 0px; border-top-color: rgb(34, 3=
4, 34); border-top-style: none; border-top-width: 0px; margin-bottom: 0px; =
margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; =
padding-left: 0px; padding-right: 0px; padding-top: 0px;"><div style=3D"bor=
der-bottom-color: rgb(34, 34, 34); border-bottom-style: none; border-bottom=
-width: 0px; border-image-outset: 0; border-image-repeat: stretch; border-i=
mage-slice: 100%; border-image-source: none; border-image-width: 1; border-=
left-color: rgb(34, 34, 34); border-left-style: none; border-left-width: 0p=
x; border-right-color: rgb(34, 34, 34); border-right-style: none; border-ri=
ght-width: 0px; border-top-color: rgb(34, 34, 34); border-top-style: none; =
border-top-width: 0px; margin-bottom: 0px; margin-left: 0px; margin-right: =
0px; margin-top: 0px; overflow: auto; padding-bottom: 0px; padding-left: 0p=
x; padding-right: 0px; padding-top: 0px;"><div style=3D"border-bottom-color=
: rgb(34, 34, 34); border-bottom-style: none; border-bottom-width: 0px; bor=
der-image-outset: 0; border-image-repeat: stretch; border-image-slice: 100%=
; border-image-source: none; border-image-width: 1; border-left-color: rgb(=
34, 34, 34); border-left-style: none; border-left-width: 0px; border-right-=
color: rgb(34, 34, 34); border-right-style: none; border-right-width: 0px; =
border-top-color: rgb(34, 34, 34); border-top-style: none; border-top-width=
: 0px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top:=
 0px; max-height: 10000px; padding-bottom: 0px; padding-left: 0px; padding-=
right: 0px; padding-top: 0px;"><div style=3D"border-bottom-color: rgb(34, 3=
4, 34); border-bottom-style: none; border-bottom-width: 0px; border-image-o=
utset: 0; border-image-repeat: stretch; border-image-slice: 100%; border-im=
age-source: none; border-image-width: 1; border-left-color: rgb(34, 34, 34)=
; border-left-style: none; border-left-width: 0px; border-right-color: rgb(=
34, 34, 34); border-right-style: none; border-right-width: 0px; border-top-=
color: rgb(34, 34, 34); border-top-style: none; border-top-width: 0px; marg=
in-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; paddi=
ng-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px;" d=
ir=3D"ltr"><div style=3D"border-bottom-color: rgb(34, 34, 34); border-botto=
m-style: none; border-bottom-width: 0px; border-image-outset: 0; border-ima=
ge-repeat: stretch; border-image-slice: 100%; border-image-source: none; bo=
rder-image-width: 1; border-left-color: rgb(34, 34, 34); border-left-style:=
 none; border-left-width: 0px; border-right-color: rgb(34, 34, 34); border-=
right-style: none; border-right-width: 0px; border-top-color: rgb(34, 34, 3=
4); border-top-style: none; border-top-width: 0px; margin-bottom: 0px; marg=
in-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padd=
ing-left: 0px; padding-right: 0px; padding-top: 0px;">Hello Mr. Pasa,</div>=
<div style=3D"border-bottom-color: rgb(34, 34, 34); border-bottom-style: no=
ne; border-bottom-width: 0px; border-image-outset: 0; border-image-repeat: =
stretch; border-image-slice: 100%; border-image-source: none; border-image-=
width: 1; border-left-color: rgb(34, 34, 34); border-left-style: none; bord=
er-left-width: 0px; border-right-color: rgb(34, 34, 34); border-right-style=
: none; border-right-width: 0px; border-top-color: rgb(34, 34, 34); border-=
top-style: none; border-top-width: 0px; margin-bottom: 0px; margin-left: 0p=
x; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0=
px; padding-right: 0px; padding-top: 0px;"><br></div><div style=3D"border-b=
ottom-color: rgb(34, 34, 34); border-bottom-style: none; border-bottom-widt=
h: 0px; border-image-outset: 0; border-image-repeat: stretch; border-image-=
slice: 100%; border-image-source: none; border-image-width: 1; border-left-=
color: rgb(34, 34, 34); border-left-style: none; border-left-width: 0px; bo=
rder-right-color: rgb(34, 34, 34); border-right-style: none; border-right-w=
idth: 0px; border-top-color: rgb(34, 34, 34); border-top-style: none; borde=
r-top-width: 0px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; =
margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px=
; padding-top: 0px;">You are right. I don&#39;t know how the map works inte=
rnally, but i know about clusters.<br>In a clusters, the worst case is push=
_front(), then the maximum number of items<br>has to be moved. I&#39;m goin=
g to add this test as worst case scenario to the specification.</div><div s=
tyle=3D"border-bottom-color: rgb(34, 34, 34); border-bottom-style: none; bo=
rder-bottom-width: 0px; border-image-outset: 0; border-image-repeat: stretc=
h; border-image-slice: 100%; border-image-source: none; border-image-width:=
 1; border-left-color: rgb(34, 34, 34); border-left-style: none; border-lef=
t-width: 0px; border-right-color: rgb(34, 34, 34); border-right-style: none=
; border-right-width: 0px; border-top-color: rgb(34, 34, 34); border-top-st=
yle: none; border-top-width: 0px; margin-bottom: 0px; margin-left: 0px; mar=
gin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; pa=
dding-right: 0px; padding-top: 0px;"><br></div><div style=3D"border-bottom-=
color: rgb(34, 34, 34); border-bottom-style: none; border-bottom-width: 0px=
; border-image-outset: 0; border-image-repeat: stretch; border-image-slice:=
 100%; border-image-source: none; border-image-width: 1; border-left-color:=
 rgb(34, 34, 34); border-left-style: none; border-left-width: 0px; border-r=
ight-color: rgb(34, 34, 34); border-right-style: none; border-right-width: =
0px; border-top-color: rgb(34, 34, 34); border-top-style: none; border-top-=
width: 0px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin=
-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padd=
ing-top: 0px;">The groups in a cluster are half-full at minimum, except the=
re is only one group.<br>This means there is an overhead of about 100% at m=
aximum.<br>The overhead for parent-groups is about 100 pointers per 10.000 =
items.<br>With a minimal item-size of 1 byte, this would be another 4%.<br>=
The maximum overhead is then 104%.<br>With an item-size less the size of 3 =
pointers, the cluster can also save memory.</div><div style=3D"border-botto=
m-color: rgb(34, 34, 34); border-bottom-style: none; border-bottom-width: 0=
px; border-image-outset: 0; border-image-repeat: stretch; border-image-slic=
e: 100%; border-image-source: none; border-image-width: 1; border-left-colo=
r: rgb(34, 34, 34); border-left-style: none; border-left-width: 0px; border=
-right-color: rgb(34, 34, 34); border-right-style: none; border-right-width=
: 0px; border-top-color: rgb(34, 34, 34); border-top-style: none; border-to=
p-width: 0px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; marg=
in-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; pa=
dding-top: 0px;"><br></div><div style=3D"border-bottom-color: rgb(34, 34, 3=
4); border-bottom-style: none; border-bottom-width: 0px; border-image-outse=
t: 0; border-image-repeat: stretch; border-image-slice: 100%; border-image-=
source: none; border-image-width: 1; border-left-color: rgb(34, 34, 34); bo=
rder-left-style: none; border-left-width: 0px; border-right-color: rgb(34, =
34, 34); border-right-style: none; border-right-width: 0px; border-top-colo=
r: rgb(34, 34, 34); border-top-style: none; border-top-width: 0px; margin-b=
ottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-b=
ottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px;">Best =
regards,</div><div style=3D"border-bottom-color: rgb(34, 34, 34); border-bo=
ttom-style: none; border-bottom-width: 0px; border-image-outset: 0; border-=
image-repeat: stretch; border-image-slice: 100%; border-image-source: none;=
 border-image-width: 1; border-left-color: rgb(34, 34, 34); border-left-sty=
le: none; border-left-width: 0px; border-right-color: rgb(34, 34, 34); bord=
er-right-style: none; border-right-width: 0px; border-top-color: rgb(34, 34=
, 34); border-top-style: none; border-top-width: 0px; margin-bottom: 0px; m=
argin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; p=
adding-left: 0px; padding-right: 0px; padding-top: 0px;">Sven<br></div><div=
 style=3D"border-bottom-color: rgb(34, 34, 34); border-bottom-style: none; =
border-bottom-width: 0px; border-image-outset: 0; border-image-repeat: stre=
tch; border-image-slice: 100%; border-image-source: none; border-image-widt=
h: 1; border-left-color: rgb(34, 34, 34); border-left-style: none; border-l=
eft-width: 0px; border-right-color: rgb(34, 34, 34); border-right-style: no=
ne; border-right-width: 0px; border-top-color: rgb(34, 34, 34); border-top-=
style: none; border-top-width: 0px; margin-bottom: 0px; margin-left: 0px; m=
argin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; =
padding-right: 0px; padding-top: 0px;"></div></div></div></div></div></div>=
   <div style=3D"border-bottom-color: rgb(34, 34, 34); border-bottom-style:=
 none; border-bottom-width: 0px; border-image-outset: 0; border-image-repea=
t: stretch; border-image-slice: 100%; border-image-source: none; border-ima=
ge-width: 1; border-left-color: rgb(34, 34, 34); border-left-style: none; b=
order-left-width: 0px; border-right-color: rgb(34, 34, 34); border-right-st=
yle: none; border-right-width: 0px; border-top-color: rgb(34, 34, 34); bord=
er-top-style: none; border-top-width: 0px; margin-bottom: 0px; margin-left:=
 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left=
: 0px; padding-right: 0px; padding-top: 0px;"></div> <div style=3D"border-b=
ottom-color: rgb(34, 34, 34); border-bottom-style: none; border-bottom-widt=
h: 0px; border-image-outset: 0; border-image-repeat: stretch; border-image-=
slice: 100%; border-image-source: none; border-image-width: 1; border-left-=
color: rgb(34, 34, 34); border-left-style: none; border-left-width: 0px; bo=
rder-right-color: rgb(34, 34, 34); border-right-style: none; border-right-w=
idth: 0px; border-top-color: rgb(34, 34, 34); border-top-style: none; borde=
r-top-width: 0px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; =
margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px=
; padding-top: 0px;"></div>   </div><span style=3D"display: inline !importa=
nt; float: none; background-color: transparent; color: rgb(34, 34, 34); fon=
t-family: &quot;Arial&quot;,&quot;Helvetica&quot;,sans-serif; font-size: 13=
px; font-style: normal; font-variant: normal; font-weight: 400; letter-spac=
ing: normal; orphans: 2; text-align: left; text-decoration: none; text-inde=
nt: 0px; text-transform: none; -webkit-text-stroke-width: 0px; white-space:=
 normal; word-spacing: 0px;"> </span><div style=3D"background-color: transp=
arent; border-bottom-color: rgb(34, 34, 34); border-bottom-style: none; bor=
der-bottom-width: 0px; border-image-outset: 0; border-image-repeat: stretch=
; border-image-slice: 100%; border-image-source: none; border-image-width: =
1; border-left-color: rgb(34, 34, 34); border-left-style: none; border-left=
-width: 0px; border-right-color: rgb(34, 34, 34); border-right-style: none;=
 border-right-width: 0px; border-top-color: rgb(34, 34, 34); border-top-sty=
le: none; border-top-width: 0px; color: rgb(34, 34, 34); font-family: &amp;=
quot;Arial&amp;quot;,&amp;quot;Helvetica&amp;quot;,sans-serif; font-size: 1=
3px; font-style: normal; font-variant: normal; font-weight: 400; letter-spa=
cing: normal; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; marg=
in-top: 0px; orphans: 2; padding-bottom: 0px; padding-left: 0px; padding-ri=
ght: 0px; padding-top: 0px; text-align: left; text-decoration: none; text-i=
ndent: 0px; text-transform: none; -webkit-text-stroke-width: 0px; white-spa=
ce: normal; word-spacing: 0px;"><div class=3D"F0XO1GC-ed-a" style=3D"border=
-bottom-color: rgb(34, 34, 34); border-bottom-style: none; border-bottom-wi=
dth: 0px; border-image-outset: 0; border-image-repeat: stretch; border-imag=
e-slice: 100%; border-image-source: none; border-image-width: 1; border-lef=
t-color: rgb(34, 34, 34); border-left-style: none; border-left-width: 0px; =
border-right-color: rgb(34, 34, 34); border-right-style: none; border-right=
-width: 0px; border-top-color: rgb(34, 34, 34); border-top-style: none; bor=
der-top-width: 0px; margin-bottom: 0px; margin-left: 44px; margin-right: 0p=
x; margin-top: 0px; padding-bottom: 0px; padding-left: 5px; padding-right: =
0px; padding-top: 0px;"></div></div><span style=3D"display: inline !importa=
nt; float: none; background-color: transparent; color: rgb(34, 34, 34); fon=
t-family: &quot;Arial&quot;,&quot;Helvetica&quot;,sans-serif; font-size: 13=
px; font-style: normal; font-variant: normal; font-weight: 400; letter-spac=
ing: normal; orphans: 2; text-align: left; text-decoration: none; text-inde=
nt: 0px; text-transform: none; -webkit-text-stroke-width: 0px; white-space:=
 normal; word-spacing: 0px;">  </span><div class=3D"F0XO1GC-nb-b" style=3D"=
background-color: transparent; border-bottom-color: rgb(34, 34, 34); border=
-bottom-style: none; border-bottom-width: 0px; border-image-outset: 0; bord=
er-image-repeat: stretch; border-image-slice: 100%; border-image-source: no=
ne; border-image-width: 1; border-left-color: rgb(34, 34, 34); border-left-=
style: none; border-left-width: 0px; border-right-color: rgb(34, 34, 34); b=
order-right-style: none; border-right-width: 0px; border-top-color: rgb(34,=
 34, 34); border-top-style: none; border-top-width: 0px; color: rgb(34, 34,=
 34); font-family: &amp;quot;Arial&amp;quot;,&amp;quot;Helvetica&amp;quot;,=
sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font=
-weight: 400; letter-spacing: normal; margin-bottom: 0px; margin-left: 39px=
; margin-right: 0px; margin-top: 0px; orphans: 2; padding-bottom: 0px; padd=
ing-left: 5px; padding-right: 0px; padding-top: 0px; text-align: left; text=
-decoration: none; text-indent: 0px; text-transform: none; -webkit-text-str=
oke-width: 0px; white-space: normal; word-spacing: 0px;"> <div class=3D"F0X=
O1GC-nb-a F0XO1GC-nb-cb" style=3D"border-bottom-color: rgb(34, 34, 34); bor=
der-bottom-style: none; border-bottom-width: 0px; border-image-outset: 0; b=
order-image-repeat: stretch; border-image-slice: 100%; border-image-source:=
 none; border-image-width: 1; border-left-color: rgb(34, 34, 34); border-le=
ft-style: none; border-left-width: 0px; border-right-color: rgb(34, 34, 34)=
; border-right-style: none; border-right-width: 0px; border-top-color: rgb(=
34, 34, 34); border-top-style: none; border-top-width: 0px; display: block;=
 margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; =
padding-bottom: 4px; padding-left: 0px; padding-right: 0px; padding-top: 4p=
x; position: relative;"> <div style=3D"border-bottom-color: rgb(34, 34, 34)=
; border-bottom-style: none; border-bottom-width: 0px; border-image-outset:=
 0; border-image-repeat: stretch; border-image-slice: 100%; border-image-so=
urce: none; border-image-width: 1; border-left-color: rgb(34, 34, 34); bord=
er-left-style: none; border-left-width: 0px; border-right-color: rgb(34, 34=
, 34); border-right-style: none; border-right-width: 0px; border-top-color:=
 rgb(34, 34, 34); border-top-style: none; border-top-width: 0px; margin-bot=
tom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bot=
tom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px;"> <div s=
tyle=3D"border-bottom-color: rgb(34, 34, 34); border-bottom-style: none; bo=
rder-bottom-width: 0px; border-image-outset: 0; border-image-repeat: stretc=
h; border-image-slice: 100%; border-image-source: none; border-image-width:=
 1; border-left-color: rgb(34, 34, 34); border-left-style: none; border-lef=
t-width: 0px; border-right-color: rgb(34, 34, 34); border-right-style: none=
; border-right-width: 0px; border-top-color: rgb(34, 34, 34); border-top-st=
yle: none; border-top-width: 0px; display: inline-block; margin-bottom: 0px=
; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px=
; padding-left: 0px; padding-right: 0px; padding-top: 0px;">   </div> </div=
></div></div><b></b><i></i><u></u><sub></sub><sup></sup><strike></strike><b=
r></div></div></div></div></div></div></div></div></div></div></div></div><=
/div></div><b></b><i></i><u></u><sub></sub><sup></sup><strike></strike><br>=
</div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/51cf2db1-b868-4404-b9e1-fabb37491c8a%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/51cf2db1-b868-4404-b9e1-fabb37491c8a=
%40isocpp.org</a>.<br />

------=_Part_1291_538400092.1540732448267--

------=_Part_1290_1197905954.1540732448267--

.

Author: svenbieg@web.de
Date: Sun, 28 Oct 2018 09:52:38 -0700 (PDT) Raw View 
------=_Part_1335_105951919.1540745558805
Content-Type: text/plain; charset="UTF-8"

Hello Mr. Pasa,

You are right, my tests are not scientific. I don't know how the map works internally, but i know about clusters.
In a cluster, the worst case is push_front(), then the maximum number of items has to be moved. I'm going to add this test as worst case scenario to the specification.

The groups in a cluster are half-full at minimum, except there is only one group.
This means there is an overhead of about 100% at maximum.
The overhead for parent-groups is about 100 pointers per 5.000 items.
With a minimal item-size of 1 byte, this would be another 8%.
Parent-groups in higher levels are below one percent.
The maximum overhead is then 109%.
With an item-size less the size of 3 pointers, the cluster could save memory for sure.

Best regards,
Sven

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/212fad4c-5646-4a02-a359-bc8927e5b4d0%40isocpp.org.

------=_Part_1335_105951919.1540745558805--

.

Author: svenbieg@web.de
Date: Sun, 28 Oct 2018 11:02:37 -0700 (PDT) Raw View 
------=_Part_116_1411561178.1540749757802
Content-Type: text/plain; charset="UTF-8"

Hello Mr. Pasa,

You are right, my tests are not scientific. I don't even know how the map works internally, but i know about clusters.
In a cluster, the worst case is push_front(), then the maximum number of items has to be moved. I'm going to add this test as worst case scenario to the specification.

The groups in a cluster are half-full at minimum, except there is only one group.
With a minimal item-size of 1 byte, there is an overhead of about 104% on the lowest level at maximum.
The overhead for parent-groups is about 100 pointers per 2.500 items, with half-full parent-groups and half-full item-groups, this is about 16%.
Parent-groups on higher levels are below 2 percent.
The maximum overhead is 118% then.
With an item-size less the size of 3 pointers, the cluster would save memory, having more than 50 items. Of course, having many clusters with only a few items could increase memory usage, but with a benefit in speed.

Best regards,
Sven

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/b3f2d267-738e-4d80-9d04-5d479030bc0a%40isocpp.org.

------=_Part_116_1411561178.1540749757802--

.

Author: Magnus Fromreide <magfr@lysator.liu.se>
Date: Sun, 28 Oct 2018 20:08:22 +0100 Raw View 
On Sun, Oct 28, 2018 at 11:02:37AM -0700, svenbieg@web.de wrote:
> Hello Mr. Pasa,
>
> You are right, my tests are not scientific. I don't even know how the map works internally, but i know about clusters.
> In a cluster, the worst case is push_front(), then the maximum number of items has to be moved. I'm going to add this test as worst case scenario to the specification.
>
> The groups in a cluster are half-full at minimum, except there is only one group.
> With a minimal item-size of 1 byte, there is an overhead of about 104% on the lowest level at maximum.
> The overhead for parent-groups is about 100 pointers per 2.500 items, with half-full parent-groups and half-full item-groups, this is about 16%.
> Parent-groups on higher levels are below 2 percent.
> The maximum overhead is 118% then.

I think this is wrong - consider the case of a cluster containing a single
element - would not that get considerably worse overhead than 118%? From the
description I'd guess that cluster would have a memory overhead in the
vicinity of 10000%.

/MF

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/20181028190821.GA3522%40noemi.bahnhof.se.

.

Author: svenbieg@web.de
Date: Sun, 28 Oct 2018 12:23:52 -0700 (PDT) Raw View 
------=_Part_1451_1736782279.1540754632224
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

This is right Mr. Fromreide,

the point is that one item is not a list. There may be an overhead of 10000=
%,
but this is only 100 times the item-size. With pointers as items, this woul=
d be only 400 bytes. The custom allocators are not mentioned here, wich cau=
se an additional overhead, too. Think of an index-cluster in memory-managem=
ent, sorting free space by size!

Best regards,

Sven

--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/2913b535-a55a-40bf-8c2c-f1664589bcaf%40isocpp.or=
g.

------=_Part_1451_1736782279.1540754632224--

.

Author: svenbieg@web.de
Date: Tue, 13 Nov 2018 12:37:11 -0800 (PST) Raw View 
------=_Part_2720_266827165.1542141432083
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

I've written a tiny operating-system for my pc as a hobby many years ago, t=
he winters are long in Germany. At some point i needed a file-system for th=
e different drivers, but i didn't want to name these system-files. I though=
t it should be possible to access these files directly from the root-direct=
ory, using an unique identifier.
First i wanted to use strings like in a dictionary, but there were not enou=
gh characters to fill one block on the hard-disk. So i built a group of ids=
 that could fill one block, and thought of this group as a single character=
.. The parent-group was then the previous character in the string. To minimi=
ze the overhead from the disk-drive, the blocks had to be as full as possib=
le. And because the drive was slow, the strings had to be as short as possi=
ble. I've now chosen c++ as language, and i'm not going to complete the ori=
ginal filesystem-driver.
The Clusters-algorithm is done and it seems to be the most powerful sorting=
 algorithm in the world! Even the btree-algorithm from Google needs double =
the time and 10% more memory. This is why i write this specification, to br=
ing Clusters into the standard-library.
Memory-allocations take a lot of time and the Clusters-algorithm in memory-=
management can bring a big benefit to the general public.
When i was writing the algorithm i found, that the algorithm could also be =
used for serialization only, without sorting. This can drastically reduce m=
emory allocations, but only if the data may be fragmented. A double success=
!

Best regards,

Sven Bieg

--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/e62cbadc-9be8-4da4-9f4d-1ba336480b35%40isocpp.or=
g.

------=_Part_2720_266827165.1542141432083--

.

Author: "masse.nicolas@gmail.com" <masse.nicolas@gmail.com>
Date: Mon, 26 Nov 2018 11:52:52 -0800 (PST) Raw View 
------=_Part_1309_22655307.1543261972267
Content-Type: multipart/alternative;
 boundary="----=_Part_1310_2020031957.1543261972267"

------=_Part_1310_2020031957.1543261972267
Content-Type: text/plain; charset="UTF-8"

Hi,

I didn't went into the details of your algorithm, but it seems you achieve
interesting results. Still, I believe that what you've done is more a
matter of implementation than a matter of specification. The things is that
specification is more about how you can expects your container to behave
(what will work, what won't, what's the expected complexity of the
different operations, ...) than how you did implement it.
For example, if you take a look at
https://en.cppreference.com/w/cpp/container, you'll see 2 table.
The 1st one is about how does the iterator behave in terms of validity.
The 2nd is about the possible operations per container-type.

I think that filling those 2 tables for your structure could be a good
starting point.
Just my 2 cents, though.

Nicolas.

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/3a46ba8a-a5ae-41db-9c24-f95c849f8705%40isocpp.org.

------=_Part_1310_2020031957.1543261972267
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>Hi,</div><div><br></div><div>I didn&#39;t went into t=
he details of your algorithm, but it seems you achieve interesting results.=
 Still, I believe that what you&#39;ve done is more a matter of implementat=
ion than a matter of specification. The things is that specification is mor=
e about how you can expects your container to behave (what will work, what =
won&#39;t, what&#39;s the expected complexity of the different operations, =
....) than how you did implement it.</div><div>For example, if you take a lo=
ok at https://en.cppreference.com/w/cpp/container, you&#39;ll see 2 table.<=
/div><div>The 1st one is about how does the iterator behave in terms of val=
idity.</div><div>The 2nd is about the possible operations per container-typ=
e.</div><div><br></div><div>I think that filling those 2 tables for your st=
ructure could be a good starting point.</div><div>Just my 2 cents, though.<=
/div><div><br></div><div>Nicolas.<br></div><div><br></div></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/3a46ba8a-a5ae-41db-9c24-f95c849f8705%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/3a46ba8a-a5ae-41db-9c24-f95c849f8705=
%40isocpp.org</a>.<br />

------=_Part_1310_2020031957.1543261972267--

------=_Part_1309_22655307.1543261972267--

.

Author: svenbieg@web.de
Date: Mon, 26 Nov 2018 12:26:54 -0800 (PST) Raw View 
------=_Part_1428_1200957320.1543264014370
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

It is unbelievable, the algorithm gets faster with a growing number of item=
s. The time for each opreation grows linear, while the number of items grow=
s exponential. Typical for each pyramid. You are right, the working impleme=
ntation ist worth more than every specification. But not all people interes=
ted in Clusters do accept machine-language. I'm going to add a worst case s=
cenario to the specification plus some credits. I'm glad to See You anyway.=
 Feel free to use Clusters and tell everybody!

Best regards,

Sven

--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/f5944970-eaa9-4d06-a1e1-6b5a693d5d58%40isocpp.or=
g.

------=_Part_1428_1200957320.1543264014370--

.