Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

The bug starts here.


devel / comp.lang.python / Re: Non-deterministic set ordering

SubjectAuthor
o Re: Non-deterministic set orderingMRAB

1
Re: Non-deterministic set ordering

<mailman.425.1652672607.20749.python-list@python.org>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=18288&group=comp.lang.python#18288

  copy link   Newsgroups: comp.lang.python
Path: i2pn2.org!i2pn.org!news.swapon.de!fu-berlin.de!uni-berlin.de!not-for-mail
From: pyt...@mrabarnett.plus.com (MRAB)
Newsgroups: comp.lang.python
Subject: Re: Non-deterministic set ordering
Date: Mon, 16 May 2022 04:40:17 +0100
Lines: 47
Message-ID: <mailman.425.1652672607.20749.python-list@python.org>
References: <d93aad1d-8586-b844-d3de-fa9648535244@btinternet.com>
<CAGGBd_p3SqB-GRBW+DdTY6++DmJ2qHfJtQUK1u2Y18CG3nWuEA@mail.gmail.com>
<d26dd6fb-ff48-1269-6e2a-acd69e5fc3f6@btinternet.com>
<06218b48-ecaa-24fc-3a60-5f29b81ffaff@mrabarnett.plus.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: news.uni-berlin.de 5erUuY7ZW2aZW6hnZYtIGABDTorqvF03xSa13bzsOVmA==
Return-Path: <python@mrabarnett.plus.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
Authentication-Results: mail.python.org; dkim=pass
reason="2048-bit key; unprotected key"
header.d=plus.com header.i=@plus.com header.b=NP5ybi+b;
dkim-adsp=none (unprotected policy); dkim-atps=neutral
X-Spam-Status: OK 0.015
X-Spam-Evidence: '*H*': 0.97; '*S*': 0.00; '2022': 0.05; 'sun,': 0.07;
'dan': 0.09; 'from:addr:python': 0.09; 'identical': 0.09;
'order,': 0.09; 'received:192.168.1.64': 0.09; '"real"': 0.16;
'assuming': 0.16; 'dicts': 0.16; 'from:addr:mrabarnett.plus.com':
0.16; 'from:name:mrab': 0.16; 'hash': 0.16; 'insertion': 0.16;
'message-id:@mrabarnett.plus.com': 0.16; 'operations,': 0.16;
'order?': 0.16; 'received:plus.net': 0.16; 'tasks.': 0.16;
'wrote:': 0.16; 'python': 0.16; 'uses': 0.19; 'round': 0.19;
'to:addr:python-list': 0.20; 'code': 0.23; 'list,': 0.24;
'anyone': 0.25; 'seems': 0.26; 'output': 0.28; 'header:User-
Agent:1': 0.30; 'program': 0.31; '(as': 0.32; 'python-list': 0.32;
"wouldn't": 0.32; 'received:192.168.1': 0.32; 'but': 0.32; "i'm":
0.33; 'same': 0.34; 'header:In-Reply-To:1': 0.34; 'running': 0.34;
'subject:skip:d 10': 0.35; 'following': 0.35; 'thanks,': 0.36;
'received:192.168': 0.37; 'developers': 0.39; 'use': 0.39;
'explain': 0.40; 'something': 0.40; 'should': 0.40; 'remember':
0.61; 'received:212': 0.62; 'come': 0.62; 'your': 0.64; 'produce':
0.65; 'operations': 0.68; 'order': 0.69; 'order.': 0.69;
'repeatedly': 0.69; 'within': 0.69; 'discover': 0.80; 'attacks.':
0.84; 'ordering': 0.84; 'rob': 0.84; 'subject:Non': 0.84;
'\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0': 0.84; 'shocked': 0.93
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=plus.com; s=042019;
t=1652672419; bh=VTsZyXGkV+RNkDAeM+ClVTdZm4y7S3CMa6dpWBhfjD8=;
h=Date:Subject:To:References:From:In-Reply-To;
b=NP5ybi+bwzXE9Yi7eB5vAMOs41deS7cL6m/4r7+seXINU3ZKA0ddlIgpV8zHaW/HY
4nyE2/L5IMVEOpoa2iEvm8hpA7e5mEoqjg0WfqkCgCuucCJ+cqTXl8q5okBZp4H1br
sh5553rSBI9hzm8QPKnjTpECJ0+8Q/i9psG1ldlp3r5p4gu2d/P4LcnzGBzIrffWJe
R9bcglRHWaSZh+I4U3GcO5nY/XlfQP4ySVSTmAz9WiQjLGOZ8/yuyfk5NPCovXCywO
KtFWUbDBmIfXZl2gwzdM3gBaJXuz23KssMgscWedU1PdPP9kqiTdIQiobwsnUAduam
gvDsg1SPeH0tg==
X-Clacks-Overhead: "GNU Terry Pratchett"
X-CM-Score: 0.00
X-CNFS-Analysis: v=2.4 cv=D+hUl9dj c=1 sm=1 tr=0 ts=6281c7a3
a=0nF1XD0wxitMEM03M9B4ZQ==:117 a=0nF1XD0wxitMEM03M9B4ZQ==:17
a=IkcTkHD0fZMA:10 a=8AHkEIZyAAAA:8 a=Lg9G_lHUAAAA:8 a=KcgxLYeEETSkENu5t_cA:9
a=QEXdDO2ut3YA:10 a=z6eu0OAp_RcA:10 a=iPyZjTF4xHxEIkEBSkWx:22
X-AUTH: mrabarnett@:2500
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Content-Language: en-GB
In-Reply-To: <d26dd6fb-ff48-1269-6e2a-acd69e5fc3f6@btinternet.com>
X-CMAE-Envelope: MS4xfEY0+FkQWM+hICWIPzzNEj+XniI6dHfJFUdCgLjQhu7UqW3VZxKKzM709LwYxiDZdliCXv8XHotyuMOeJxrKcF+xx+/8cmmrAMbthyGe/Zyo2wSMwp9b
tPy72FvDbW8ukICkxthehN1WowNxbsODxeiYsc0ty6BT6LoO3VIV+VnbSFnQrkamSOTS+kQGCW0kGbXWmS49iXWbQ3xdiQ0OW7Y=
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.39
Precedence: list
List-Id: General discussion list for the Python programming language
<python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>,
<mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <https://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>,
<mailto:python-list-request@python.org?subject=subscribe>
X-Mailman-Original-Message-ID: <06218b48-ecaa-24fc-3a60-5f29b81ffaff@mrabarnett.plus.com>
X-Mailman-Original-References: <d93aad1d-8586-b844-d3de-fa9648535244@btinternet.com>
<CAGGBd_p3SqB-GRBW+DdTY6++DmJ2qHfJtQUK1u2Y18CG3nWuEA@mail.gmail.com>
<d26dd6fb-ff48-1269-6e2a-acd69e5fc3f6@btinternet.com>
 by: MRAB - Mon, 16 May 2022 03:40 UTC

On 2022-05-16 04:20, Rob Cliffe via Python-list wrote:
>
>
> On 16/05/2022 04:13, Dan Stromberg wrote:
>>
>> On Sun, May 15, 2022 at 8:01 PM Rob Cliffe via Python-list
>> <python-list@python.org> wrote:
>>
>> I was shocked to discover that when repeatedly running the following
>> program (condensed from a "real" program) under Python 3.8.3
>>
>> for p in { ('x','y'), ('y','x') }:
>>      print(p)
>>
>> the output was sometimes
>>
>> ('y', 'x')
>> ('x', 'y')
>>
>> and sometimes
>>
>> ('x', 'y')
>> ('y', 'x')
>>
>> Can anyone explain why running identical code should result in
>> traversing a set in a different order?
>>
>>
>> Sets are defined as unordered so that they can be hashed internally to
>> give O(1) operations for many tasks.
>>
>> It wouldn't be unreasonable for sets to use a fixed-by-arbitrary
>> ordering for a given group of set operations, but being unpredictable
>> deters developers from mistakenly assuming they are ordered.
>>
>> If you need order, you should use a tuple, list, or something like
>> https://grantjenks.com/docs/sortedcontainers/sortedset.html
> Thanks, I can work round this behaviour.
> But I'm curious: where does the variability come from?  Is it deliberate
> (as your answer seems to imply)?  AFAIK the same code within the *same
> run* of a program does produce identical results.

Basically, Python uses hash randomisation in order to protect it against
denial-of-service attacks. (Search for "PYTHONHASHSEED" in the docs.)

It also applied to dicts (the code for sets was based on that for
dicts), but dicts now remember their insertion order.

1
server_pubkey.txt

rocksolid light 0.9.8
clearnet tor