Difference between revisions of "User:Ssvb"
(→Associative arrays and hash collisions) |
(→Associative arrays and hash collisions) |
||
| Line 45: | Line 45: | ||
https://forum.dlang.org/post/navsnrjweslsqeaawsev@forum.dlang.org | https://forum.dlang.org/post/navsnrjweslsqeaawsev@forum.dlang.org | ||
| + | |||
| + | A hacked solution on codeforces: https://codeforces.com/contest/1676/submission/156707849 | ||
Relevant links: | Relevant links: | ||
| Line 53: | Line 55: | ||
* https://github.com/tkaitchuck/aHash/blob/master/compare/readme.md | * https://github.com/tkaitchuck/aHash/blob/master/compare/readme.md | ||
* https://www.josephkirwin.com/2018/04/07/z3-hash-inversions | * https://www.josephkirwin.com/2018/04/07/z3-hash-inversions | ||
| + | * http://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/ | ||
Revision as of 06:33, 23 May 2022
Contents
D language for programming competitions
Not everything is perfect:
- Hash tables are vulnerable: https://issues.dlang.org/show_bug.cgi?id=7179 and https://codeforces.com/contest/1676/submission/156707849
- Arithmetic overflows detection is not the best
- 128-bit data type is missing
- std.bigint is slow (not using GMP as a backend)
- std.random is slow: https://codeforces.com/blog/entry/99292#comment-881097
GDC tips and tricks
GDC 11+ requires "-flto" or "-fno-weak-templates" option to avoid a major performance regression: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102765
Shared library linking workaround to run phobos unit tests: https://bugzilla.gdcproject.org/show_bug.cgi?id=199
Demangle symbols: https://dlang.org/phobos/std_demangle.html
Mingw build and test instructions: TODO
Arithmetic overflows
TODO: create a new DIP? https://forum.dlang.org/post/rclilxjpnjvexggncfhd@forum.dlang.org
TODO: Atomic operations and arithmetic overflows?
TODO: Unsigned overflows?
GDC supports "-ftrapv" easter egg option for trapping signed overflows.
Relevant links:
- https://dlang.org/phobos/core_checkedint.html
- https://forum.dlang.org/post/s3dm64$2f2i$1@digitalmars.com
- https://news.ycombinator.com/item?id=24575780
- https://gcc.gnu.org/legacy-ml/gcc/2014-07/msg00251.html
- https://gcc.gnu.org/onlinedocs/gccint/Integer-library-routines.html
GCC history of -fno-strict-aliasing and -fwrapv:
- https://www.mail-archive.com/redhat-list@redhat.com/msg18009.html
- https://lists.gnu.org/archive/html/autoconf-patches/2006-12/msg00091.html
- https://lists.gnu.org/archive/html/bug-gnulib/2006-12/msg00094.html
- https://gcc.gnu.org/legacy-ml/gcc/2008-02/msg00732.html
Associative arrays and hash collisions
https://forum.dlang.org/post/navsnrjweslsqeaawsev@forum.dlang.org
A hacked solution on codeforces: https://codeforces.com/contest/1676/submission/156707849
Relevant links:
- https://en.wikipedia.org/wiki/Collision_attack#Hash_flooding
- https://en.wikipedia.org/wiki/SipHash
- https://github.com/google/highwayhash ("Defending against hash flooding" section)
- https://github.com/google/highwayhash/issues/28
- https://github.com/tkaitchuck/aHash/blob/master/compare/readme.md
- https://www.josephkirwin.com/2018/04/07/z3-hash-inversions
- http://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/
