summaryrefslogtreecommitdiff
path: root/rts/Hash.c
Commit message (Collapse)AuthorAgeFilesLines
* Expunge #ifdef and #ifndef from the codebaseJohn Ericson2019-07-141-1/+1
| | | | | | | | These are unexploded minds as far as the linter is concerned. I don't want to hit in my MRs by mistake! I did this with `sed`, and then rolled back some changes in the docs, config.guess, and the linter itself.
* Fix a few GCC warningsMichal Terepeta2018-05-131-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | GCC 8 now generates warnings for incompatible function pointer casts [-Werror=cast-function-type]. Apparently there are a few of those in rts code, which makes `./validate` unhappy (since we compile with `-Werror`) This commit tries to fix these issues by changing the functions to have the correct type (and, if necessary, moving the casts into those functions). For instance, hash/comparison function are declared (`Hash.h`) to take `StgWord` but we want to use `StgWord64[2]` in `StaticPtrTable.c`. Instead of casting the function pointers, we can cast the `StgWord` parameter to `StgWord*`. I think this should be ok since `StgWord` should be the same size as a pointer. Signed-off-by: Michal Terepeta <michal.terepeta@gmail.com> Test Plan: ./validate Reviewers: bgamari, erikd, simonmar Reviewed By: bgamari Subscribers: rwbarton, thomie, carter Differential Revision: https://phabricator.haskell.org/D4673
* rts: Fix use of #ifBen Gamari2017-09-061-1/+1
|
* Replace hashing function for string keys implementation with xxhashTamar Christina2017-09-051-10/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | When doing profiling on startup time of ghci on Windows, both cold and startup loading static LLVM libs, the profiler is showing a glaring red spot on the division operation of the the hashStr function. In fact profiling shows 14% of the time is spent hashing the keys. So I am replacing the hash function with xxHash which is a very fast non-crypto hash. It's faster than MurMurHash which node etc use. It also passes SMHasher. I can provide if required the collected raw data. But from analysis done on the keys, xxHash does not introduce more collisions than before, the amount splits seem about the same and the distributions among the buckets are slightly more uniform than before. However the runtime dropped enough to remove the function completely from the profiler's report. There's also a noticeable improvement in responsiveness. xxHash is BSD licensed and can be found https://github.com/Cyan4973/xxHash Test Plan: ./validate Reviewers: austin, bgamari, erikd, simonmar Reviewed By: bgamari Subscribers: rwbarton, thomie GHC Trac Issues: #13165 Differential Revision: https://phabricator.haskell.org/D3909
* Overhaul of Compact Regions (#12455)Simon Marlow2016-12-071-2/+31
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This commit makes various improvements and addresses some issues with Compact Regions (aka Compact Normal Forms). This was the most important thing I wanted to fix. Compaction previously prevented GC from running until it was complete, which would be a problem in a multicore setting. Now, we compact using a hand-written Cmm routine that can be interrupted at any point. When a GC is triggered during a sharing-enabled compaction, the GC has to traverse and update the hash table, so this hash table is now stored in the StgCompactNFData object. Previously, compaction consisted of a deepseq using the NFData class, followed by a traversal in C code to copy the data. This is now done in a single pass with hand-written Cmm (see rts/Compact.cmm). We no longer use the NFData instances, instead the Cmm routine evaluates components directly as it compacts. The new compaction is about 50% faster than the old one with no sharing, and a little faster on average with sharing (the cost of the hash table dominates when we're doing sharing). Static objects that don't (transitively) refer to any CAFs don't need to be copied into the compact region. In particular this means we often avoid copying Char values and small Int values, because these are static closures in the runtime. Each Compact# object can support a single compactAdd# operation at any given time, so the Data.Compact library now enforces mutual exclusion using an MVar stored in the Compact object. We now get exceptions rather than killing everything with a barf() when we encounter an object that cannot be compacted (a function, or a mutable object). We now also detect pinned objects, which can't be compacted either. The Data.Compact API has been refactored and cleaned up. A new compactSize operation returns the size (in bytes) of the compact object. Most of the documentation is in the Haddock docs for the compact library, which I've expanded and improved here. Various comments in the code have been improved, especially the main Note [Compact Normal Forms] in rts/sm/CNF.c. I've added a few tests, and expanded a few of the tests that were there. We now also run the tests with GHCi, and in a new test way that enables sanity checking (+RTS -DS). There's a benchmark in libraries/compact/tests/compact_bench.hs for measuring compaction speed and comparing sharing vs. no sharing. The field totalDataW in StgCompactNFData was unnecessary. Test Plan: * new unit tests * validate * tested manually that we can compact Data.Aeson data Reviewers: gcampax, bgamari, ezyang, austin, niteria, hvr, erikd Subscribers: thomie, simonpj Differential Revision: https://phabricator.haskell.org/D2751 GHC Trac Issues: #12455
* rts: Add missing `const` from HashTable APIErik de Castro Lopo2016-05-191-1/+1
| | | | | | | | | | | | | | Thanks to Tamar Christina (Phyx) for spotting this. Test Plan: Validate Reviewers: simonmar, austin, trofi, bgamari, hsyl20, Phyx Reviewed By: Phyx Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D2236
* rts: More const correct-ness fixesErik de Castro Lopo2016-05-181-5/+5
| | | | | | | | | | | | | | | | | | | | In addition to more const-correctness fixes this patch fixes an infelicity of the previous const-correctness patch (995cf0f356) which left `UNTAG_CLOSURE` taking a `const StgClosure` pointer parameter but returning a non-const pointer. Here we restore the original type signature of `UNTAG_CLOSURE` and add a new function `UNTAG_CONST_CLOSURE` which takes and returns a const `StgClosure` pointer and uses that wherever possible. Test Plan: Validate on Linux, OS X and Windows Reviewers: Phyx, hsyl20, bgamari, austin, simonmar, trofi Reviewed By: simonmar, trofi Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D2231
* rts/Hash: Constify HashTable* in lookupHashTableBen Gamari2015-11-031-3/+3
| | | | | | | | This seems like an obvious place to apply `const` Reviewed By: simonmar, austin Differential Revision: https://phabricator.haskell.org/D1416
* Trac #9878: Make the static form illegal in interpreted mode.Alexander Vershilov2015-01-161-8/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The entries of the static pointers table are expected to exist as object code. Thus we have ghci complain with an intelligible error message if the static form is used in interpreted mode. It also includes a fix to keysHashTable in Hash.c which could cause a crash. The iteration of the hashtable internals was incorrect. This patch has the function keysHashTable imitate the iteration in freeHashTable. Finally, we submit here some minor edits to comments and GHC.StaticPtr.StaticPtrInfo field names. Authored-by: Alexander Vershilov <alexander.vershilov@tweag. Authored-by: Facundo Domínguez <facundo.dominguez@tweag.io> Test Plan: ./validate Reviewers: simonpj, hvr, austin Reviewed By: austin Subscribers: carter, thomie, qnikst, mboes Differential Revision: https://phabricator.haskell.org/D586 GHC Trac Issues: #9878
* Groom comments related to StaticPointers.Facundo Domínguez2014-12-221-1/+1
| | | | | | Reviewed By: austin Differential Revision: https://phabricator.haskell.org/D575
* Implement -XStaticValuesFacundo Domínguez2014-12-091-0/+23
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: As proposed in [1], this extension introduces a new syntactic form `static e`, where `e :: a` can be any closed expression. The static form produces a value of type `StaticPtr a`, which works as a reference that programs can "dereference" to get the value of `e` back. References are like `Ptr`s, except that they are stable across invocations of a program. The relevant wiki pages are [2, 3], which describe the motivation/ideas and implementation plan respectively. [1] Jeff Epstein, Andrew P. Black, and Simon Peyton-Jones. Towards Haskell in the cloud. SIGPLAN Not., 46(12):118–129, September 2011. ISSN 0362-1340. [2] https://ghc.haskell.org/trac/ghc/wiki/StaticPointers [3] https://ghc.haskell.org/trac/ghc/wiki/StaticPointers/ImplementationPlan Authored-by: Facundo Domínguez <facundo.dominguez@tweag.io> Authored-by: Mathieu Boespflug <m@tweag.io> Authored-by: Alexander Vershilov <alexander.vershilov@tweag.io> Test Plan: `./validate` Reviewers: hvr, simonmar, simonpj, austin Reviewed By: simonpj, austin Subscribers: qnikst, bgamari, mboes, carter, thomie, goldfire Differential Revision: https://phabricator.haskell.org/D550 GHC Trac Issues: #7015
* Revert "rts: add Emacs 'Local Variables' to every .c file"Simon Marlow2014-09-291-8/+0
| | | | This reverts commit 39b5c1cbd8950755de400933cecca7b8deb4ffcd.
* rts: add Emacs 'Local Variables' to every .c fileAustin Seipp2014-07-281-0/+8
| | | | | | | | This will hopefully help ensure some basic consistency in the forward by overriding buffer variables. In particular, it sets the wrap length, the offset to 4, and turns off tabs. Signed-off-by: Austin Seipp <austin@well-typed.com>
* rts: delint/detab/dewhitespace Hash.cAustin Seipp2014-07-281-64/+64
| | | | Signed-off-by: Austin Seipp <austin@well-typed.com>
* Separate StablePtr and StableName tables (#7674)Simon Marlow2013-02-141-0/+5
| | | | To improve performance of StablePtr.
* The hash table implementation had some static free lists that wereSimon Marlow2011-04-151-34/+33
| | | | | | | | not protected by locks in the threaded RTS. This moves the free lists to the individual hash tables and removes the static variables. Spotted by Marcin Orczyk <orczykm@dcs.gla.ac.uk>, thanks! This could definitely cause actual crashes.
* RTS tidyup sweep, first phaseSimon Marlow2009-08-021-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The first phase of this tidyup is focussed on the header files, and in particular making sure we are exposinng publicly exactly what we need to, and no more. - Rts.h now includes everything that the RTS exposes publicly, rather than a random subset of it. - Most of the public header files have moved into subdirectories, and many of them have been renamed. But clients should not need to include any of the other headers directly, just #include the main public headers: Rts.h, HsFFI.h, RtsAPI.h. - All the headers needed for via-C compilation have moved into the stg subdirectory, which is self-contained. Most of the headers for the rest of the RTS APIs have moved into the rts subdirectory. - I left MachDeps.h where it is, because it is so widely used in Haskell code. - I left a deprecated stub for RtsFlags.h in place. The flag structures are now exposed by Rts.h. - Various internal APIs are no longer exposed by public header files. - Various bits of dead code and declarations have been removed - More gcc warnings are turned on, and the RTS code is more warning-clean. - More source files #include "PosixSource.h", and hence only use standard POSIX (1003.1c-1995) interfaces. There is a lot more tidying up still to do, this is just the first pass. I also intend to standardise the names for external RTS APIs (e.g use the rts_ prefix consistently), and declare the internal APIs as hidden for shared libraries.
* Move file locking into the RTS, fixing #629, #1109Simon Marlow2007-11-201-6/+3
| | | | | | | | | | | | | | | File locking (of the Haskell 98 variety) was previously done using a static table with linear search, which had two problems: the array had a fixed size and was sometimes too small (#1109), and performance of lockFile/unlockFile was suboptimal due to the linear search. Also the algorithm failed to count readers as required by Haskell 98 (#629). Now it's done using a hash table (provided by the RTS). Furthermore I avoided the extra fstat() for every open file by passing the dev_t and ino_t into lockFile. This and the improvements to the locking algorithm result in a healthy 20% or so performance increase for opening/closing files (see openFile008 test).
* Remember to free() memory on exitSimon Marlow2006-08-081-0/+22
| | | | | Patch mostly from Lennart Augustsson in #803, with additions to Task.c by me.
* Reorganisation of the source treeSimon Marlow2006-04-071-0/+376
Most of the other users of the fptools build system have migrated to Cabal, and with the move to darcs we can now flatten the source tree without losing history, so here goes. The main change is that the ghc/ subdir is gone, and most of what it contained is now at the top level. The build system now makes no pretense at being multi-project, it is just the GHC build system. No doubt this will break many things, and there will be a period of instability while we fix the dependencies. A straightforward build should work, but I haven't yet fixed binary/source distributions. Changes to the Building Guide will follow, too.
View Lorry Controller Status