You can subscribe to this list here.
| 2002 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
|
Aug
|
Sep
(1) |
Oct
(122) |
Nov
(152) |
Dec
(69) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2003 |
Jan
(6) |
Feb
(25) |
Mar
(73) |
Apr
(82) |
May
(24) |
Jun
(25) |
Jul
(10) |
Aug
(11) |
Sep
(10) |
Oct
(54) |
Nov
(203) |
Dec
(182) |
| 2004 |
Jan
(307) |
Feb
(305) |
Mar
(430) |
Apr
(312) |
May
(187) |
Jun
(342) |
Jul
(487) |
Aug
(637) |
Sep
(336) |
Oct
(373) |
Nov
(441) |
Dec
(210) |
| 2005 |
Jan
(385) |
Feb
(480) |
Mar
(636) |
Apr
(544) |
May
(679) |
Jun
(625) |
Jul
(810) |
Aug
(838) |
Sep
(634) |
Oct
(521) |
Nov
(965) |
Dec
(543) |
| 2006 |
Jan
(494) |
Feb
(431) |
Mar
(546) |
Apr
(411) |
May
(406) |
Jun
(322) |
Jul
(256) |
Aug
(401) |
Sep
(345) |
Oct
(542) |
Nov
(308) |
Dec
(481) |
| 2007 |
Jan
(427) |
Feb
(326) |
Mar
(367) |
Apr
(255) |
May
(244) |
Jun
(204) |
Jul
(223) |
Aug
(231) |
Sep
(354) |
Oct
(374) |
Nov
(497) |
Dec
(362) |
| 2008 |
Jan
(322) |
Feb
(482) |
Mar
(658) |
Apr
(422) |
May
(476) |
Jun
(396) |
Jul
(455) |
Aug
(267) |
Sep
(280) |
Oct
(253) |
Nov
(232) |
Dec
(304) |
| 2009 |
Jan
(486) |
Feb
(470) |
Mar
(458) |
Apr
(423) |
May
(696) |
Jun
(461) |
Jul
(551) |
Aug
(575) |
Sep
(134) |
Oct
(110) |
Nov
(157) |
Dec
(102) |
| 2010 |
Jan
(226) |
Feb
(86) |
Mar
(147) |
Apr
(117) |
May
(107) |
Jun
(203) |
Jul
(193) |
Aug
(238) |
Sep
(300) |
Oct
(246) |
Nov
(23) |
Dec
(75) |
| 2011 |
Jan
(133) |
Feb
(195) |
Mar
(315) |
Apr
(200) |
May
(267) |
Jun
(293) |
Jul
(353) |
Aug
(237) |
Sep
(278) |
Oct
(611) |
Nov
(274) |
Dec
(260) |
| 2012 |
Jan
(303) |
Feb
(391) |
Mar
(417) |
Apr
(441) |
May
(488) |
Jun
(655) |
Jul
(590) |
Aug
(610) |
Sep
(526) |
Oct
(478) |
Nov
(359) |
Dec
(372) |
| 2013 |
Jan
(467) |
Feb
(226) |
Mar
(391) |
Apr
(281) |
May
(299) |
Jun
(252) |
Jul
(311) |
Aug
(352) |
Sep
(481) |
Oct
(571) |
Nov
(222) |
Dec
(231) |
| 2014 |
Jan
(185) |
Feb
(329) |
Mar
(245) |
Apr
(238) |
May
(281) |
Jun
(399) |
Jul
(382) |
Aug
(500) |
Sep
(579) |
Oct
(435) |
Nov
(487) |
Dec
(256) |
| 2015 |
Jan
(338) |
Feb
(357) |
Mar
(330) |
Apr
(294) |
May
(191) |
Jun
(108) |
Jul
(142) |
Aug
(261) |
Sep
(190) |
Oct
(54) |
Nov
(83) |
Dec
(22) |
| 2016 |
Jan
(49) |
Feb
(89) |
Mar
(33) |
Apr
(50) |
May
(27) |
Jun
(34) |
Jul
(53) |
Aug
(53) |
Sep
(98) |
Oct
(206) |
Nov
(93) |
Dec
(53) |
| 2017 |
Jan
(65) |
Feb
(82) |
Mar
(102) |
Apr
(86) |
May
(187) |
Jun
(67) |
Jul
(23) |
Aug
(93) |
Sep
(65) |
Oct
(45) |
Nov
(35) |
Dec
(17) |
| 2018 |
Jan
(26) |
Feb
(35) |
Mar
(38) |
Apr
(32) |
May
(8) |
Jun
(43) |
Jul
(27) |
Aug
(30) |
Sep
(43) |
Oct
(42) |
Nov
(38) |
Dec
(67) |
| 2019 |
Jan
(32) |
Feb
(37) |
Mar
(53) |
Apr
(64) |
May
(49) |
Jun
(18) |
Jul
(14) |
Aug
(53) |
Sep
(25) |
Oct
(30) |
Nov
(49) |
Dec
(31) |
| 2020 |
Jan
(87) |
Feb
(45) |
Mar
(37) |
Apr
(51) |
May
(99) |
Jun
(36) |
Jul
(11) |
Aug
(14) |
Sep
(20) |
Oct
(24) |
Nov
(40) |
Dec
(23) |
| 2021 |
Jan
(14) |
Feb
(53) |
Mar
(85) |
Apr
(15) |
May
(19) |
Jun
(3) |
Jul
(14) |
Aug
(1) |
Sep
(57) |
Oct
(73) |
Nov
(56) |
Dec
(22) |
| 2022 |
Jan
(3) |
Feb
(22) |
Mar
(6) |
Apr
(55) |
May
(46) |
Jun
(39) |
Jul
(15) |
Aug
(9) |
Sep
(11) |
Oct
(34) |
Nov
(20) |
Dec
(36) |
| 2023 |
Jan
(79) |
Feb
(41) |
Mar
(99) |
Apr
(169) |
May
(48) |
Jun
(16) |
Jul
(16) |
Aug
(57) |
Sep
(19) |
Oct
|
Nov
|
Dec
|
| S | M | T | W | T | F | S |
|---|---|---|---|---|---|---|
|
|
|
|
|
|
1
(6) |
2
(7) |
|
3
(12) |
4
(9) |
5
(12) |
6
(9) |
7
(18) |
8
(10) |
9
(17) |
|
10
(15) |
11
(22) |
12
(16) |
13
(18) |
14
(9) |
15
(14) |
16
(18) |
|
17
(24) |
18
(11) |
19
(15) |
20
(29) |
21
(19) |
22
(20) |
23
(9) |
|
24
(25) |
25
(25) |
26
(38) |
27
(22) |
28
(16) |
29
(17) |
|
|
From: Bart V. A. <bar...@gm...> - 2008-02-18 20:01:24
|
One of the criticisms on happens-before data race detection tools like Intel Thread Checker and exp-drd is that these tools can miss some violations of a locking discipline. Small examples that illustrate this are well known, and are a.o. published in the original paper about the Eraser algorithm. Since some time I am wondering what the chance is that a happens-before detector misses a locking discipline in a realistic program. Does anyone know whether any papers have been published on this subject ? Some authors argue that data that is shared over threads and protected by mutexes is almost always accessed many times which makes the chance low that locking discipline violations go undetected. Bart. |
|
From: Bart V. A. <bar...@gm...> - 2008-02-18 18:33:07
|
On Feb 17, 2008 9:57 PM, Nicholas Nethercote <nj...@cs...> wrote: > On Sun, 17 Feb 2008 sv...@va... wrote: > > +to and reading from the shared memory. Since the invention of the > > +multithreading concept, there is an ongoing debate about which way to > > +model concurrent activities is better -- shared memory programming or > > +message passing [Ousterhout 1996]. > > Isn't what you've called here "multithreading" more typically called "shared > memory multithreading" or something like that? The threads that exist within a single process share memory by definition. The historical perspective is as follows: * The first computers did not have an OS and ran one program at a time. * The first operating systems were capable to run multiple processes, but all these processes consisted of a single thread. * The concepts of mutual exclusion and semaphores were already described by Per Brinch Hansen in his paper "A comparison of two synchronizing concepts" (Acta Informatica, 1972). * The monitor concept was introduced by C.A.R. Hoare in his publication titled "Monitors: An Operating System Structuring Concept" (Communications of the ACM, October 1974). * The oldest publication I could find in which the thread concept was mentioned dates from 1986: "Mach: A New Kernel Foundation For UNIX Development" by Accetta et al. (USENIX 1986). > Nice write-up, BTW. Thanks :-) Bart. |
|
From: Tom H. <th...@cy...> - 2008-02-18 05:10:06
|
Nightly build on alvis ( i686, Red Hat 7.3 ) started at 2008-02-18 03:15:10 GMT Results unchanged from 24 hours ago Checking out valgrind source tree ... done Configuring valgrind ... done Building valgrind ... done Running regression tests ... failed Regression test results follow == 338 tests, 80 stderr failures, 1 stdout failure, 29 post failures == memcheck/tests/addressable (stderr) memcheck/tests/badjump (stderr) memcheck/tests/describe-block (stderr) memcheck/tests/erringfds (stderr) memcheck/tests/leak-0 (stderr) memcheck/tests/leak-cycle (stderr) memcheck/tests/leak-pool-0 (stderr) memcheck/tests/leak-pool-1 (stderr) memcheck/tests/leak-pool-2 (stderr) memcheck/tests/leak-pool-3 (stderr) memcheck/tests/leak-pool-4 (stderr) memcheck/tests/leak-pool-5 (stderr) memcheck/tests/leak-regroot (stderr) memcheck/tests/leak-tree (stderr) memcheck/tests/long_namespace_xml (stderr) memcheck/tests/lsframe1 (stderr) memcheck/tests/lsframe2 (stderr) memcheck/tests/malloc_free_fill (stderr) memcheck/tests/match-overrun (stderr) memcheck/tests/noisy_child (stderr) memcheck/tests/partial_load_dflt (stderr) memcheck/tests/partial_load_ok (stderr) memcheck/tests/partiallydefinedeq (stderr) memcheck/tests/pointer-trace (stderr) memcheck/tests/sigkill (stderr) memcheck/tests/stack_changes (stderr) memcheck/tests/x86/bug152022 (stderr) memcheck/tests/x86/scalar (stderr) memcheck/tests/x86/scalar_supp (stderr) memcheck/tests/x86/xor-undef-x86 (stderr) memcheck/tests/xml1 (stderr) massif/tests/alloc-fns-A (post) massif/tests/alloc-fns-B (post) massif/tests/basic (post) massif/tests/basic2 (post) massif/tests/big-alloc (post) massif/tests/culling1 (stderr) massif/tests/culling2 (stderr) massif/tests/custom_alloc (post) massif/tests/deep-A (post) massif/tests/deep-B (stderr) massif/tests/deep-B (post) massif/tests/deep-C (stderr) massif/tests/deep-C (post) massif/tests/deep-D (post) massif/tests/ignoring (post) massif/tests/insig (post) massif/tests/long-names (post) massif/tests/long-time (post) massif/tests/new-cpp (post) massif/tests/null (post) massif/tests/one (post) massif/tests/overloaded-new (post) massif/tests/peak (post) massif/tests/peak2 (stderr) massif/tests/peak2 (post) massif/tests/realloc (stderr) massif/tests/realloc (post) massif/tests/thresholds_0_0 (post) massif/tests/thresholds_0_10 (post) massif/tests/thresholds_10_0 (post) massif/tests/thresholds_10_10 (post) massif/tests/thresholds_5_0 (post) massif/tests/thresholds_5_10 (post) massif/tests/zero1 (post) massif/tests/zero2 (post) none/tests/blockfault (stderr) none/tests/mremap (stderr) none/tests/mremap2 (stdout) helgrind/tests/hg01_all_ok (stderr) helgrind/tests/hg02_deadlock (stderr) helgrind/tests/hg03_inherit (stderr) helgrind/tests/hg04_race (stderr) helgrind/tests/hg05_race2 (stderr) helgrind/tests/hg06_readshared (stderr) helgrind/tests/tc01_simple_race (stderr) helgrind/tests/tc02_simple_tls (stderr) helgrind/tests/tc03_re_excl (stderr) helgrind/tests/tc05_simple_race (stderr) helgrind/tests/tc06_two_races (stderr) helgrind/tests/tc07_hbl1 (stderr) helgrind/tests/tc08_hbl2 (stderr) helgrind/tests/tc09_bad_unlock (stderr) helgrind/tests/tc11_XCHG (stderr) helgrind/tests/tc12_rwl_trivial (stderr) helgrind/tests/tc14_laog_dinphils (stderr) helgrind/tests/tc16_byterace (stderr) helgrind/tests/tc17_sembar (stderr) helgrind/tests/tc18_semabuse (stderr) helgrind/tests/tc19_shadowmem (stderr) helgrind/tests/tc20_verifywrap (stderr) helgrind/tests/tc21_pthonce (stderr) helgrind/tests/tc22_exit_w_lock (stderr) helgrind/tests/tc23_bogus_condwait (stderr) helgrind/tests/tc24_nonzero_sem (stderr) exp-drd/tests/fp_race (stderr) exp-drd/tests/fp_race2 (stderr) exp-drd/tests/matinv (stderr) exp-drd/tests/pth_barrier (stderr) exp-drd/tests/pth_broadcast (stderr) exp-drd/tests/pth_cond_race (stderr) exp-drd/tests/pth_cond_race2 (stderr) exp-drd/tests/pth_create_chain (stderr) exp-drd/tests/pth_detached (stderr) exp-drd/tests/pth_detached2 (stderr) exp-drd/tests/sem_as_mutex (stderr) exp-drd/tests/sem_as_mutex2 (stderr) exp-drd/tests/sigalrm (stderr) exp-drd/tests/tc17_sembar (stderr) exp-drd/tests/tc18_semabuse (stderr) |
|
From: Tom H. <th...@cy...> - 2008-02-18 04:05:47
|
Nightly build on lloyd ( x86_64, Fedora 7 ) started at 2008-02-18 03:05:04 GMT Results unchanged from 24 hours ago Checking out valgrind source tree ... done Configuring valgrind ... done Building valgrind ... done Running regression tests ... failed Regression test results follow == 372 tests, 7 stderr failures, 2 stdout failures, 0 post failures == memcheck/tests/malloc_free_fill (stderr) memcheck/tests/pointer-trace (stderr) memcheck/tests/vcpu_fnfns (stdout) memcheck/tests/x86/scalar (stderr) memcheck/tests/xml1 (stderr) none/tests/mremap (stderr) none/tests/mremap2 (stdout) helgrind/tests/tc20_verifywrap (stderr) helgrind/tests/tc22_exit_w_lock (stderr) |
|
From: Tom H. <th...@cy...> - 2008-02-18 03:47:32
|
Nightly build on aston ( x86_64, Fedora Core 5 ) started at 2008-02-18 03:20:08 GMT Results unchanged from 24 hours ago Checking out valgrind source tree ... done Configuring valgrind ... done Building valgrind ... done Running regression tests ... failed Regression test results follow == 378 tests, 9 stderr failures, 1 stdout failure, 0 post failures == memcheck/tests/malloc_free_fill (stderr) memcheck/tests/pointer-trace (stderr) memcheck/tests/x86/scalar (stderr) memcheck/tests/xml1 (stderr) none/tests/blockfault (stderr) none/tests/mremap (stderr) none/tests/mremap2 (stdout) none/tests/sem (stderr) helgrind/tests/tc20_verifywrap (stderr) helgrind/tests/tc22_exit_w_lock (stderr) |
|
From: Tom H. <th...@cy...> - 2008-02-18 03:42:18
|
Nightly build on trojan ( x86_64, Fedora Core 6 ) started at 2008-02-18 03:25:17 GMT Results differ from 24 hours ago Checking out valgrind source tree ... done Configuring valgrind ... done Building valgrind ... done Running regression tests ... failed Regression test results follow == 376 tests, 6 stderr failures, 5 stdout failures, 0 post failures == memcheck/tests/pointer-trace (stderr) memcheck/tests/vcpu_fnfns (stdout) memcheck/tests/x86/bug133694 (stdout) memcheck/tests/x86/bug133694 (stderr) memcheck/tests/x86/scalar (stderr) none/tests/cmdline1 (stdout) none/tests/cmdline2 (stdout) none/tests/mremap (stderr) none/tests/mremap2 (stdout) helgrind/tests/tc20_verifywrap (stderr) helgrind/tests/tc22_exit_w_lock (stderr) ================================================= == Results from 24 hours ago == ================================================= Checking out valgrind source tree ... done Configuring valgrind ... done Building valgrind ... done Running regression tests ... failed Regression test results follow == 376 tests, 7 stderr failures, 5 stdout failures, 0 post failures == memcheck/tests/pointer-trace (stderr) memcheck/tests/vcpu_fnfns (stdout) memcheck/tests/x86/bug133694 (stdout) memcheck/tests/x86/bug133694 (stderr) memcheck/tests/x86/scalar (stderr) none/tests/cmdline1 (stdout) none/tests/cmdline2 (stdout) none/tests/mremap (stderr) none/tests/mremap2 (stdout) helgrind/tests/tc17_sembar (stderr) helgrind/tests/tc20_verifywrap (stderr) helgrind/tests/tc22_exit_w_lock (stderr) ================================================= == Difference between 24 hours ago and now == ================================================= *** old.short Mon Feb 18 03:35:57 2008 --- new.short Mon Feb 18 03:42:22 2008 *************** *** 8,10 **** ! == 376 tests, 7 stderr failures, 5 stdout failures, 0 post failures == memcheck/tests/pointer-trace (stderr) --- 8,10 ---- ! == 376 tests, 6 stderr failures, 5 stdout failures, 0 post failures == memcheck/tests/pointer-trace (stderr) *************** *** 18,20 **** none/tests/mremap2 (stdout) - helgrind/tests/tc17_sembar (stderr) helgrind/tests/tc20_verifywrap (stderr) --- 18,19 ---- |
|
From: Tom H. <th...@cy...> - 2008-02-18 03:27:33
|
Nightly build on dellow ( x86_64, Fedora 8 ) started at 2008-02-18 03:10:04 GMT Results differ from 24 hours ago Checking out valgrind source tree ... done Configuring valgrind ... done Building valgrind ... done Running regression tests ... failed Regression test results follow == 372 tests, 8 stderr failures, 2 stdout failures, 0 post failures == memcheck/tests/malloc_free_fill (stderr) memcheck/tests/pointer-trace (stderr) memcheck/tests/vcpu_fnfns (stdout) memcheck/tests/x86/scalar (stderr) memcheck/tests/xml1 (stderr) none/tests/mremap (stderr) none/tests/mremap2 (stdout) helgrind/tests/tc18_semabuse (stderr) helgrind/tests/tc20_verifywrap (stderr) helgrind/tests/tc22_exit_w_lock (stderr) ================================================= == Results from 24 hours ago == ================================================= Checking out valgrind source tree ... done Configuring valgrind ... done Building valgrind ... done Running regression tests ... failed Regression test results follow == 372 tests, 10 stderr failures, 2 stdout failures, 0 post failures == memcheck/tests/malloc_free_fill (stderr) memcheck/tests/pointer-trace (stderr) memcheck/tests/vcpu_fnfns (stdout) memcheck/tests/x86/scalar (stderr) memcheck/tests/xml1 (stderr) none/tests/mremap (stderr) none/tests/mremap2 (stdout) helgrind/tests/tc17_sembar (stderr) helgrind/tests/tc18_semabuse (stderr) helgrind/tests/tc20_verifywrap (stderr) helgrind/tests/tc22_exit_w_lock (stderr) exp-drd/tests/tc18_semabuse (stderr) ================================================= == Difference between 24 hours ago and now == ================================================= *** old.short Mon Feb 18 03:18:37 2008 --- new.short Mon Feb 18 03:27:35 2008 *************** *** 8,10 **** ! == 372 tests, 10 stderr failures, 2 stdout failures, 0 post failures == memcheck/tests/malloc_free_fill (stderr) --- 8,10 ---- ! == 372 tests, 8 stderr failures, 2 stdout failures, 0 post failures == memcheck/tests/malloc_free_fill (stderr) *************** *** 16,18 **** none/tests/mremap2 (stdout) - helgrind/tests/tc17_sembar (stderr) helgrind/tests/tc18_semabuse (stderr) --- 16,17 ---- *************** *** 20,22 **** helgrind/tests/tc22_exit_w_lock (stderr) - exp-drd/tests/tc18_semabuse (stderr) --- 19,20 ---- |
|
From: Tom H. <th...@cy...> - 2008-02-18 03:14:51
|
Nightly build on gill ( x86_64, Fedora Core 2 ) started at 2008-02-18 03:00:07 GMT Results unchanged from 24 hours ago Checking out valgrind source tree ... done Configuring valgrind ... done Building valgrind ... done Running regression tests ... failed Regression test results follow == 378 tests, 29 stderr failures, 3 stdout failures, 0 post failures == memcheck/tests/malloc_free_fill (stderr) memcheck/tests/pointer-trace (stderr) memcheck/tests/stack_switch (stderr) memcheck/tests/x86/scalar (stderr) memcheck/tests/x86/scalar_supp (stderr) none/tests/amd64/insn_ssse3 (stdout) none/tests/amd64/insn_ssse3 (stderr) none/tests/amd64/ssse3_misaligned (stderr) none/tests/blockfault (stderr) none/tests/fdleak_fcntl (stderr) none/tests/mremap (stderr) none/tests/mremap2 (stdout) none/tests/x86/insn_ssse3 (stdout) none/tests/x86/insn_ssse3 (stderr) none/tests/x86/ssse3_misaligned (stderr) helgrind/tests/hg01_all_ok (stderr) helgrind/tests/hg02_deadlock (stderr) helgrind/tests/hg03_inherit (stderr) helgrind/tests/hg04_race (stderr) helgrind/tests/hg05_race2 (stderr) helgrind/tests/tc01_simple_race (stderr) helgrind/tests/tc05_simple_race (stderr) helgrind/tests/tc06_two_races (stderr) helgrind/tests/tc09_bad_unlock (stderr) helgrind/tests/tc14_laog_dinphils (stderr) helgrind/tests/tc16_byterace (stderr) helgrind/tests/tc17_sembar (stderr) helgrind/tests/tc19_shadowmem (stderr) helgrind/tests/tc20_verifywrap (stderr) helgrind/tests/tc21_pthonce (stderr) helgrind/tests/tc22_exit_w_lock (stderr) helgrind/tests/tc23_bogus_condwait (stderr) |
|
From: <sv...@va...> - 2008-02-18 02:16:18
|
Author: sewardj
Date: 2008-02-18 02:16:22 +0000 (Mon, 18 Feb 2008)
New Revision: 7424
Log:
Fix distinctly bogus comparison routine which caused the new quicksort
implementation to loop forever.
Modified:
branches/DATASYMS/memcheck/mc_leakcheck.c
Modified: branches/DATASYMS/memcheck/mc_leakcheck.c
===================================================================
--- branches/DATASYMS/memcheck/mc_leakcheck.c 2008-02-18 01:59:33 UTC (rev 7423)
+++ branches/DATASYMS/memcheck/mc_leakcheck.c 2008-02-18 02:16:22 UTC (rev 7424)
@@ -215,7 +215,9 @@
{
MC_Chunk* mc1 = *(MC_Chunk**)n1;
MC_Chunk* mc2 = *(MC_Chunk**)n2;
- return (mc1->data < mc2->data ? -1 : 1);
+ if (mc1->data < mc2->data) return -1;
+ if (mc1->data > mc2->data) return 1;
+ return 0;
}
/* If ptr is pointing to a heap-allocated block which hasn't been seen
|
|
From: <sv...@va...> - 2008-02-18 01:59:29
|
Author: sewardj
Date: 2008-02-18 01:59:33 +0000 (Mon, 18 Feb 2008)
New Revision: 7423
Log:
More minor comment and tidying changes.
Modified:
branches/DATASYMS/coregrind/m_debuginfo/readdwarf3.c
Modified: branches/DATASYMS/coregrind/m_debuginfo/readdwarf3.c
===================================================================
--- branches/DATASYMS/coregrind/m_debuginfo/readdwarf3.c 2008-02-18 01:58:23 UTC (rev 7422)
+++ branches/DATASYMS/coregrind/m_debuginfo/readdwarf3.c 2008-02-18 01:59:33 UTC (rev 7423)
@@ -83,6 +83,16 @@
In some cases, the info for a variable is split between two
different DIEs (generally a declarer and a definer). We punt on
these. Could do better here.
+
+ Improve performance. The number of type entities that end up in
+ the list of TyAdmins rapidly becomes huge (eg, for
+ libQtGui.so.4.3.2 (amd64-linux, size 80729047 bytes), there are
+ 786860 entries in the list). Mostly this seems to be caused by g++
+ adding type DIEs for all the basic types once for each source file
+ contributing to the compilation unit, and for a large library they
+ add up quickly. That causes both a lot of work for this reader
+ module, and also wastes vast amounts of memory storing this
+ duplicated information. We could surely do a lot better here.
*/
#include "pub_core_basics.h"
@@ -1758,18 +1768,6 @@
its children. */
typestack_preen( parser, td3, level-1 );
- if (0 && (dtag == DW_TAG_base_type
- || dtag == DW_TAG_pointer_type
- || dtag == DW_TAG_reference_type
- || dtag == DW_TAG_typedef
- || dtag == DW_TAG_array_type
- || dtag == DW_TAG_subrange_type
- || dtag == DW_TAG_enumeration_type
- || dtag == DW_TAG_structure_type
- || dtag == DW_TAG_union_type)) {
- TRACE_D3("YYYYXXXX offset=%ld %s\n", posn, ML_(pp_DW_TAG)(dtag));
- }
-
if (dtag == DW_TAG_compile_unit) {
/* See if we can find DW_AT_language, since it is important for
establishing array bounds (see DW_TAG_subrange_type below in
@@ -2304,6 +2302,7 @@
D3_INVALID_CUOFF, return NULL in *payload.
Otherwise (conceptually fails) and returns False. */
+__attribute__((noinline))
static Bool resolve_binding ( /*OUT*/void** payload,
XArray* map, void* cuOff,
TyAdminTag tag,
@@ -2340,6 +2339,7 @@
return True;
}
+__attribute__((noinline))
static void resolve_type_entities ( /*MOD*/TyAdmin* admin,
/*MOD*/TempVar* vars )
{
@@ -2359,6 +2359,9 @@
}
VG_(setCmpFnXA)( map, cmp_D3TyAdmin_by_cuOff );
+ if (0)
+ VG_(printf)("XXXXXX sorting map with %d entries\n",
+ (Int)VG_(sizeXA)(map));
VG_(sortXA)( map );
for (adp = admin; adp; adp = adp->next) {
@@ -2977,8 +2980,10 @@
0x0-0x11D (pre-biasing, of course). */
vg_assert(varp->pcMax < ~(Addr)0);
}
- /* NOTE: re "if": this is a hack. Really, if the type didn't
- get resolved, something's broken earlier on. */
+ /* NOTE: re "if": this is a hack. If typeR is NULL then the
+ type didn't get resolved. Really, in that case something's
+ broken earlier on, and should be fixed, rather than just
+ skipping the variable. */
if (varp->typeR)
ML_(addVar)(
di, varp->level,
|
|
From: <sv...@va...> - 2008-02-18 01:58:20
|
Author: sewardj
Date: 2008-02-18 01:58:23 +0000 (Mon, 18 Feb 2008)
New Revision: 7422
Log:
Replace VG_(ssort) -- the shellsort routine -- with a Bentley-McIlroy
style 3-way partitioning quicksort algorithm. The latter really ought
to be the gold standard in quicksorts, but doesn't seem widely used.
It uses slightly fewer instructions than the shellsort, and trashes
the caches a lot less, particularly D1, when sorting large arrays.
Consequently is considerably faster.
Modified:
branches/DATASYMS/coregrind/m_libcbase.c
Modified: branches/DATASYMS/coregrind/m_libcbase.c
===================================================================
--- branches/DATASYMS/coregrind/m_libcbase.c 2008-02-17 20:54:12 UTC (rev 7421)
+++ branches/DATASYMS/coregrind/m_libcbase.c 2008-02-18 01:58:23 UTC (rev 7422)
@@ -579,6 +579,144 @@
Misc useful functions
------------------------------------------------------------------ */
+/////////////////////////////////////////////////////////////
+/////////////////////////////////////////////////////////////
+/// begin Bentley-McIlroy style quicksort
+/// See "Engineering a Sort Function". Jon L Bentley, M. Douglas
+/// McIlroy. Software Practice and Experience Vol 23(11), Nov 1993.
+
+#define BM_MIN(a, b) \
+ (a) < (b) ? a : b
+
+#define BM_SWAPINIT(a, es) \
+ swaptype = ((a-(Char*)0) | es) % sizeof(Word) ? 2 \
+ : es > (SizeT)sizeof(Word) ? 1 \
+ : 0
+
+#define BM_EXCH(a, b, t) \
+ (t = a, a = b, b = t)
+
+#define BM_SWAP(a, b) \
+ swaptype != 0 \
+ ? bm_swapfunc(a, b, es, swaptype) \
+ : (void)BM_EXCH(*(Word*)(a), *(Word*)(b), t)
+
+#define BM_VECSWAP(a, b, n) \
+ if (n > 0) bm_swapfunc(a, b, n, swaptype)
+
+#define BM_PVINIT(pv, pm) \
+ if (swaptype != 0) \
+ pv = a, BM_SWAP(pv, pm); \
+ else \
+ pv = (Char*)&v, v = *(Word*)pm
+
+static Char* bm_med3 ( Char* a, Char* b, Char* c,
+ Int (*cmp)(void*,void*) ) {
+ return cmp(a, b) < 0
+ ? (cmp(b, c) < 0 ? b : cmp(a, c) < 0 ? c : a)
+ : (cmp(b, c) > 0 ? b : cmp(a, c) > 0 ? c : a);
+}
+
+static void bm_swapfunc ( Char* a, Char* b, SizeT n, Int swaptype )
+{
+ if (swaptype <= 1) {
+ Word t;
+ for ( ; n > 0; a += sizeof(Word), b += sizeof(Word),
+ n -= sizeof(Word))
+ BM_EXCH(*(Word*)a, *(Word*)b, t);
+ } else {
+ Char t;
+ for ( ; n > 0; a += 1, b += 1, n -= 1)
+ BM_EXCH(*a, *b, t);
+ }
+}
+
+static void bm_qsort ( Char* a, SizeT n, SizeT es,
+ Int (*cmp)(void*,void*) )
+{
+ Char *pa, *pb, *pc, *pd, *pl, *pm, *pn, *pv;
+ Int r, swaptype;
+ Word t, v;
+ SizeT s, s1, s2;
+ tailcall:
+ BM_SWAPINIT(a, es);
+ if (n < 7) {
+ for (pm = a + es; pm < a + n*es; pm += es)
+ for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es)
+ BM_SWAP(pl, pl-es);
+ return;
+ }
+ pm = a + (n/2)*es;
+ if (n > 7) {
+ pl = a;
+ pn = a + (n-1)*es;
+ if (n > 40) {
+ s = (n/8)*es;
+ pl = bm_med3(pl, pl+s, pl+2*s, cmp);
+ pm = bm_med3(pm-s, pm, pm+s, cmp);
+ pn = bm_med3(pn-2*s, pn-s, pn, cmp);
+ }
+ pm = bm_med3(pl, pm, pn, cmp);
+ }
+ BM_PVINIT(pv, pm);
+ pa = pb = a;
+ pc = pd = a + (n-1)*es;
+ for (;;) {
+ while (pb <= pc && (r = cmp(pb, pv)) <= 0) {
+ if (r == 0) { BM_SWAP(pa, pb); pa += es; }
+ pb += es;
+ }
+ while (pc >= pb && (r = cmp(pc, pv)) >= 0) {
+ if (r == 0) { BM_SWAP(pc, pd); pd -= es; }
+ pc -= es;
+ }
+ if (pb > pc) break;
+ BM_SWAP(pb, pc);
+ pb += es;
+ pc -= es;
+ }
+ pn = a + n*es;
+ s = BM_MIN(pa-a, pb-pa ); BM_VECSWAP(a, pb-s, s);
+ s = BM_MIN(pd-pc, pn-pd-es); BM_VECSWAP(pb, pn-s, s);
+ /* Now recurse. Do the smaller partition first with an explicit
+ recursion, then do the larger partition using a tail call.
+ Except we can't rely on gcc to implement a tail call in any sane
+ way, so simply jump back to the start. This guarantees stack
+ growth can never exceed O(log N) even in the worst case. */
+ s1 = pb-pa;
+ s2 = pd-pc;
+ if (s1 < s2) {
+ if (s1 > es) {
+ bm_qsort(a, s1/es, es, cmp);
+ }
+ if (s2 > es) {
+ /* bm_qsort(pn-s2, s2/es, es, cmp); */
+ a = pn-s2; n = s2/es; es = es; cmp = cmp;
+ goto tailcall;
+ }
+ } else {
+ if (s2 > es) {
+ bm_qsort(pn-s2, s2/es, es, cmp);
+ }
+ if (s1 > es) {
+ /* bm_qsort(a, s1/es, es, cmp); */
+ a = a; n = s1/es; es = es; cmp = cmp;
+ goto tailcall;
+ }
+ }
+}
+
+#undef BM_MIN
+#undef BM_SWAPINIT
+#undef BM_EXCH
+#undef BM_SWAP
+#undef BM_VECSWAP
+#undef BM_PVINIT
+
+/// end Bentley-McIlroy style quicksort
+/////////////////////////////////////////////////////////////
+/////////////////////////////////////////////////////////////
+
/* Returns the base-2 logarithm of x. Returns -1 if x is not a power
of two. */
Int VG_(log2) ( UInt x )
@@ -596,110 +734,10 @@
void VG_(ssort)( void* base, SizeT nmemb, SizeT size,
Int (*compar)(void*, void*) )
{
- Int incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,
- 9841, 29524, 88573, 265720,
- 797161, 2391484 };
- Int lo = 0;
- Int hi = nmemb-1;
- Int i, j, h, bigN, hp;
+ bm_qsort(base,nmemb,size,compar);
+}
- bigN = hi - lo + 1; if (bigN < 2) return;
- hp = 0; while (hp < 14 && incs[hp] < bigN) hp++; hp--;
- #define SORT \
- for ( ; hp >= 0; hp--) { \
- h = incs[hp]; \
- for (i = lo + h; i <= hi; i++) { \
- ASSIGN(v,0, a,i); \
- j = i; \
- while (COMPAR(a,(j-h), v,0) > 0) { \
- ASSIGN(a,j, a,(j-h)); \
- j = j - h; \
- if (j <= (lo + h - 1)) break; \
- } \
- ASSIGN(a,j, v,0); \
- } \
- }
-
- // Specialised cases
- if (sizeof(ULong) == size) {
-
- #define ASSIGN(dst, dsti, src, srci) \
- (dst)[(dsti)] = (src)[(srci)];
-
- #define COMPAR(dst, dsti, src, srci) \
- compar( (void*)(& (dst)[(dsti)]), (void*)(& (src)[(srci)]) )
-
- ULong* a = (ULong*)base;
- ULong v[1];
-
- SORT;
-
- } else if (sizeof(UInt) == size) {
-
- UInt* a = (UInt*)base;
- UInt v[1];
-
- SORT;
-
- } else if (sizeof(UShort) == size) {
- UShort* a = (UShort*)base;
- UShort v[1];
-
- SORT;
-
- } else if (sizeof(UChar) == size) {
- UChar* a = (UChar*)base;
- UChar v[1];
-
- SORT;
-
- #undef ASSIGN
- #undef COMPAR
-
- } else if ( (4*sizeof(UWord)) == size ) {
- /* special-case 4 word-elements. This captures a lot of cases
- from symbol table reading/canonicalisaton, because both DiLoc
- and DiSym are 4 word structures. */
- HChar* a = base;
- HChar v[size];
-
- #define ASSIGN(dst, dsti, src, srci) \
- do { UWord* dP = (UWord*)&dst[size*(dsti)]; \
- UWord* sP = (UWord*)&src[size*(srci)]; \
- dP[0] = sP[0]; \
- dP[1] = sP[1]; \
- dP[2] = sP[2]; \
- dP[3] = sP[3]; \
- } while (0)
-
- #define COMPAR(dst, dsti, src, srci) \
- compar( &dst[size*(dsti)], &src[size*(srci)] )
-
- SORT;
-
- #undef ASSIGN
- #undef COMPAR
-
- // General case
- } else {
- HChar* a = base;
- HChar v[size]; // will be at least 'size' bytes
-
- #define ASSIGN(dst, dsti, src, srci) \
- VG_(memcpy)( &dst[size*(dsti)], &src[size*(srci)], size );
-
- #define COMPAR(dst, dsti, src, srci) \
- compar( &dst[size*(dsti)], &src[size*(srci)] )
-
- SORT;
-
- #undef ASSIGN
- #undef COMPAR
- }
- #undef SORT
-}
-
// This random number generator is based on the one suggested in Kernighan
// and Ritchie's "The C Programming Language".
|