Code:
/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / Core / System / Linq / Parallel / Partitioning / HashRepartitionStream.cs / 1305376 / HashRepartitionStream.cs
// ==++== // // Copyright (c) Microsoft Corporation. All rights reserved. // // ==--== // =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ // // HashPartitionedStream.cs // //[....] // // =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- using System.Collections.Generic; using System.Diagnostics.Contracts; using System.Threading; namespace System.Linq.Parallel { ////// A repartitioning stream must take input data that has already been partitioned and /// redistribute its contents based on a new partitioning algorithm. This is accomplished /// by making each partition p responsible for redistributing its input data to the /// correct destination partition. Some input elements may remain in p, but many will now /// belong to a different partition and will need to move. This requires a great deal of /// synchronization, but allows threads to repartition data incrementally and in parallel. /// Each partition will "pull" data on-demand instead of partitions "pushing" data, which /// allows us to reduce some amount of synchronization overhead. /// /// We currently only offer one form of reparitioning via hashing. This used to be an /// abstract base class, but we have eliminated that to get rid of some virtual calls on /// hot code paths. Uses a key selection algorithm with mod'ding to determine destination. /// /// @ internal abstract class HashRepartitionStream : PartitionedStream , TOrderKey> { private readonly IEqualityComparer m_keyComparer; // The optional key comparison routine. private readonly IEqualityComparer m_elementComparer; // The optional element comparison routine. private readonly int m_distributionMod; // The distribution value we'll use to scramble input. //---------------------------------------------------------------------------------------- // Creates a new partition exchange operator. // internal HashRepartitionStream( int partitionsCount, IComparer orderKeyComparer, IEqualityComparer hashKeyComparer, IEqualityComparer elementComparer) : base(partitionsCount, orderKeyComparer, OrdinalIndexState.Shuffled) { // elementComparer is used by operators that use elements themselves as the hash keys. // When elements are used as keys, THashKey should be NoKeyMemoizationRequired. m_keyComparer = hashKeyComparer; m_elementComparer = elementComparer; Contract.Assert(m_keyComparer == null || m_elementComparer == null); Contract.Assert(m_elementComparer == null || typeof(THashKey) == typeof(NoKeyMemoizationRequired)); // We use the following constant when distributing hash-codes into partition streams. // It's an (arbitrary) prime number to account for poor hashing functions, e.g. those // that all the primitive types use (e.g. Int32 returns itself). The goal is to add some // degree of randomization to avoid predictable distributions for certain data sequences, // for the same reason prime numbers are frequently used in hashtable implementations. // For instance, if all hash-codes end up as even, we would starve half of the partitions // by just using the raw hash-code. This isn't perfect, of course, since a stream // of integers with the same value end up in the same partition, but helps. const int DEFAULT_HASH_MOD_DISTRIBUTION = 503; // We need to guarantee our distribution mod is greater than the number of partitions. m_distributionMod = DEFAULT_HASH_MOD_DISTRIBUTION; while (m_distributionMod < partitionsCount) { // We use checked arithmetic here. We'll only overflow for huge numbers of partitions // (quite unlikely), so the remote possibility of an exception is fine. checked { m_distributionMod *= 2; } } } //--------------------------------------------------------------------------------------- // Manufactures a hash code for a given value or key. // // The hash-code used for null elements. private const int NULL_ELEMENT_HASH_CODE = 0; internal int GetHashCode(TInputOutput element) { return (0x7fffffff & (m_elementComparer == null ? (element == null ? NULL_ELEMENT_HASH_CODE : element.GetHashCode()) : m_elementComparer.GetHashCode(element))) % m_distributionMod; } internal int GetHashCode(THashKey key) { return (0x7fffffff & (m_keyComparer == null ? (key == null ? NULL_ELEMENT_HASH_CODE : key.GetHashCode()) : m_keyComparer.GetHashCode(key))) % m_distributionMod; } } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007. // ==++== // // Copyright (c) Microsoft Corporation. All rights reserved. // // ==--== // =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ // // HashPartitionedStream.cs // // [....] // // =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- using System.Collections.Generic; using System.Diagnostics.Contracts; using System.Threading; namespace System.Linq.Parallel { ////// A repartitioning stream must take input data that has already been partitioned and /// redistribute its contents based on a new partitioning algorithm. This is accomplished /// by making each partition p responsible for redistributing its input data to the /// correct destination partition. Some input elements may remain in p, but many will now /// belong to a different partition and will need to move. This requires a great deal of /// synchronization, but allows threads to repartition data incrementally and in parallel. /// Each partition will "pull" data on-demand instead of partitions "pushing" data, which /// allows us to reduce some amount of synchronization overhead. /// /// We currently only offer one form of reparitioning via hashing. This used to be an /// abstract base class, but we have eliminated that to get rid of some virtual calls on /// hot code paths. Uses a key selection algorithm with mod'ding to determine destination. /// /// @ internal abstract class HashRepartitionStream : PartitionedStream , TOrderKey> { private readonly IEqualityComparer m_keyComparer; // The optional key comparison routine. private readonly IEqualityComparer m_elementComparer; // The optional element comparison routine. private readonly int m_distributionMod; // The distribution value we'll use to scramble input. //---------------------------------------------------------------------------------------- // Creates a new partition exchange operator. // internal HashRepartitionStream( int partitionsCount, IComparer orderKeyComparer, IEqualityComparer hashKeyComparer, IEqualityComparer elementComparer) : base(partitionsCount, orderKeyComparer, OrdinalIndexState.Shuffled) { // elementComparer is used by operators that use elements themselves as the hash keys. // When elements are used as keys, THashKey should be NoKeyMemoizationRequired. m_keyComparer = hashKeyComparer; m_elementComparer = elementComparer; Contract.Assert(m_keyComparer == null || m_elementComparer == null); Contract.Assert(m_elementComparer == null || typeof(THashKey) == typeof(NoKeyMemoizationRequired)); // We use the following constant when distributing hash-codes into partition streams. // It's an (arbitrary) prime number to account for poor hashing functions, e.g. those // that all the primitive types use (e.g. Int32 returns itself). The goal is to add some // degree of randomization to avoid predictable distributions for certain data sequences, // for the same reason prime numbers are frequently used in hashtable implementations. // For instance, if all hash-codes end up as even, we would starve half of the partitions // by just using the raw hash-code. This isn't perfect, of course, since a stream // of integers with the same value end up in the same partition, but helps. const int DEFAULT_HASH_MOD_DISTRIBUTION = 503; // We need to guarantee our distribution mod is greater than the number of partitions. m_distributionMod = DEFAULT_HASH_MOD_DISTRIBUTION; while (m_distributionMod < partitionsCount) { // We use checked arithmetic here. We'll only overflow for huge numbers of partitions // (quite unlikely), so the remote possibility of an exception is fine. checked { m_distributionMod *= 2; } } } //--------------------------------------------------------------------------------------- // Manufactures a hash code for a given value or key. // // The hash-code used for null elements. private const int NULL_ELEMENT_HASH_CODE = 0; internal int GetHashCode(TInputOutput element) { return (0x7fffffff & (m_elementComparer == null ? (element == null ? NULL_ELEMENT_HASH_CODE : element.GetHashCode()) : m_elementComparer.GetHashCode(element))) % m_distributionMod; } internal int GetHashCode(THashKey key) { return (0x7fffffff & (m_keyComparer == null ? (key == null ? NULL_ELEMENT_HASH_CODE : key.GetHashCode()) : m_keyComparer.GetHashCode(key))) % m_distributionMod; } } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- invalidudtexception.cs
- GenericIdentity.cs
- EntityConnection.cs
- ControlTemplate.cs
- SecureEnvironment.cs
- DrawingState.cs
- ExceptionHandler.cs
- ParamArrayAttribute.cs
- ListItemConverter.cs
- ContextQuery.cs
- SqlProfileProvider.cs
- connectionpool.cs
- UrlPropertyAttribute.cs
- AtomContentProperty.cs
- TextEditorThreadLocalStore.cs
- NullPackagingPolicy.cs
- SessionParameter.cs
- FileVersionInfo.cs
- DiscoveryUtility.cs
- SharedPerformanceCounter.cs
- SafeCryptHandles.cs
- RegexReplacement.cs
- SelectManyQueryOperator.cs
- NumberSubstitution.cs
- ContractBase.cs
- ContainerParagraph.cs
- FlagsAttribute.cs
- TemplatedAdorner.cs
- NotSupportedException.cs
- ClientFormsAuthenticationMembershipProvider.cs
- XPathSelectionIterator.cs
- RadioButtonBaseAdapter.cs
- StylusCollection.cs
- PartBasedPackageProperties.cs
- TitleStyle.cs
- TraceListeners.cs
- UpDownBase.cs
- ParameterModifier.cs
- CredentialManagerDialog.cs
- HeaderCollection.cs
- XmlAttributeCache.cs
- UInt64.cs
- JsonFormatGeneratorStatics.cs
- EventLog.cs
- DragEventArgs.cs
- SimplePropertyEntry.cs
- DotExpr.cs
- StreamFormatter.cs
- ListBindableAttribute.cs
- ProcessThreadCollection.cs
- HttpListener.cs
- CriticalFinalizerObject.cs
- RadioButtonStandardAdapter.cs
- ThreadWorkerController.cs
- WebEvents.cs
- AVElementHelper.cs
- XamlFigureLengthSerializer.cs
- AuthorizationRuleCollection.cs
- WebHeaderCollection.cs
- XmlSchemaSet.cs
- HitTestWithGeometryDrawingContextWalker.cs
- LiteralControl.cs
- MaskDesignerDialog.cs
- ExtendedPropertyCollection.cs
- KeyEvent.cs
- XmlSchemaCollection.cs
- LoginView.cs
- InvokePatternIdentifiers.cs
- DbParameterCollectionHelper.cs
- ListViewHitTestInfo.cs
- CryptoKeySecurity.cs
- CodeSnippetTypeMember.cs
- FrameworkContentElement.cs
- WindowsBrush.cs
- ProtocolsConfigurationEntry.cs
- GridViewRowCollection.cs
- RegexCode.cs
- TextParaLineResult.cs
- ErasingStroke.cs
- Translator.cs
- VirtualDirectoryMapping.cs
- TextParagraphCache.cs
- HeaderLabel.cs
- Missing.cs
- WSTrust.cs
- BaseParagraph.cs
- SecUtil.cs
- SmiEventSink.cs
- DataBindingCollection.cs
- ParserOptions.cs
- EntityTransaction.cs
- _CacheStreams.cs
- ExpressionNormalizer.cs
- GenerateTemporaryTargetAssembly.cs
- HtmlUtf8RawTextWriter.cs
- EventLogEntry.cs
- EdmComplexPropertyAttribute.cs
- UIElement.cs
- ConfigurationManagerInternalFactory.cs
- XMLSchema.cs