Skip to content

C# extractor: Improve performance by changing the caching #615

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
hvitved merged 5 commits into from
Dec 21, 2018
Merged

C# extractor: Improve performance by changing the caching #615

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
5 commits
Select commit Hold shift + click to select a range
a7cdf52
C#: Improve performance by mapping directly from entities to labels.
calumgrant Dec 4, 2018
88734f1
C#: Fix label conflicts.
calumgrant Dec 18, 2018
93ce34a
C#: Add a new object->entity cache.
calumgrant Dec 19, 2018
6a54a6d
C#: Fix changed unit tests.
calumgrant Dec 19, 2018
d73b28e
C#: Address review comments.
calumgrant Dec 20, 2018
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
2 changes: 1 addition & 1 deletion csharp/extractor/Semmle.Extraction.CSharp/Entities/Accessor.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -58,7 +58,7 @@ public override void Populate()
}
else
{
Context.ModelError(symbol, "Undhandled accessor kind");
Context.ModelError(symbol, "Unhandled accessor kind");
return;
}

Expand Down
2 changes: 1 addition & 1 deletion csharp/extractor/Semmle.Extraction.CSharp/Entities/Constructor.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -118,7 +118,7 @@ public override IId Id
if (symbol.IsStatic) tb.Append("static");
tb.Append(ContainingType);
AddParametersToId(Context, tb, symbol);
tb.Append("; constructor");
tb.Append(";constructor");
});
}
}
Expand Down
7 changes: 4 additions & 3 deletions csharp/extractor/Semmle.Extraction.CSharp/Entities/Event.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -30,11 +30,12 @@ public override void Populate()
Context.Emit(Tuples.events(this, symbol.GetName(), ContainingType, type.TypeRef, Create(Context, symbol.OriginalDefinition)));

var adder = symbol.AddMethod;
if (adder != null)
var remover = symbol.RemoveMethod;

if (!(adder is null))
EventAccessor.Create(Context, adder);

var remover = symbol.RemoveMethod;
if (remover != null)
if (!(remover is null))
EventAccessor.Create(Context, remover);

ExtractModifiers();
Expand Down
34 changes: 5 additions & 29 deletions csharp/extractor/Semmle.Extraction.CSharp/Entities/Indexer.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -21,45 +21,21 @@ public override void Populate()
var getter = symbol.GetMethod;
var setter = symbol.SetMethod;

if (getter == null && setter == null)
if (getter is null && setter is null)
Context.ModelError(symbol, "No indexer accessor defined");

if (getter != null)
{
Getter = Accessor.Create(Context, getter);
}
if (!(getter is null))
Method.Create(Context, getter);

if (setter != null)
{
Setter = Accessor.Create(Context, setter);
}
if (!(setter is null))
Method.Create(Context, setter);

for (var i = 0; i < symbol.Parameters.Length; ++i)
{
var original = Parameter.Create(Context, symbol.OriginalDefinition.Parameters[i], OriginalDefinition);
Parameter.Create(Context, symbol.Parameters[i], this, original);
}

if (getter != null)
{
Getter = Accessor.Create(Context, getter);
Context.Emit(Tuples.accessors(Getter, 1, getter.Name, this, Getter.OriginalDefinition));

Context.Emit(Tuples.accessor_location(Getter, Getter.Location));
Getter.Overrides();
Getter.ExtractModifiers();
}

if (setter != null)
{
Setter = Accessor.Create(Context, setter);
Context.Emit(Tuples.accessors(Setter, 2, setter.Name, this, Setter.OriginalDefinition));

Context.Emit(Tuples.accessor_location(Setter, Setter.Location));
Setter.Overrides();
Setter.ExtractModifiers();
}

if (IsSourceDeclaration)
{
var expressionBody = ExpressionBody;
Expand Down
13 changes: 10 additions & 3 deletions csharp/extractor/Semmle.Extraction.CSharp/Entities/Method.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -256,21 +256,28 @@ public static Method Create(Context cx, IMethodSymbol methodDecl)
{
if (methodDecl == null) return null;

switch (methodDecl.MethodKind)
var methodKind = methodDecl.MethodKind;

if(methodKind == MethodKind.ExplicitInterfaceImplementation)
Copy link
Copy Markdown
Contributor

@hvitved hvitved Dec 19, 2018

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

space

{
// Retrieve the original method kind
methodKind = methodDecl.ExplicitInterfaceImplementations.Select(m => m.MethodKind).FirstOrDefault();
}

switch (methodKind)
{
case MethodKind.StaticConstructor:
case MethodKind.Constructor:
return Constructor.Create(cx, methodDecl);
case MethodKind.ReducedExtension:
case MethodKind.Ordinary:
case MethodKind.DelegateInvoke:
case MethodKind.ExplicitInterfaceImplementation:
return OrdinaryMethod.Create(cx, methodDecl);
case MethodKind.Destructor:
return Destructor.Create(cx, methodDecl);
case MethodKind.PropertyGet:
case MethodKind.PropertySet:
return Accessor.Create(cx, methodDecl);
return methodDecl.AssociatedSymbol is null ? OrdinaryMethod.Create(cx, methodDecl) : (Method)Accessor.Create(cx, methodDecl);
case MethodKind.EventAdd:
case MethodKind.EventRemove:
return EventAccessor.Create(cx, methodDecl);
Expand Down
13 changes: 11 additions & 2 deletions csharp/extractor/Semmle.Extraction.CSharp/Entities/Namespace.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -2,7 +2,7 @@

namespace Semmle.Extraction.CSharp.Entities
{
class Namespace : CachedEntity<INamespaceSymbol>
sealed class Namespace : CachedEntity<INamespaceSymbol>
{
Namespace(Context cx, INamespaceSymbol init)
: base(cx, init) { }
Expand Down Expand Up @@ -31,7 +31,7 @@ public override IId Id
}
}

public static Namespace Create(Context cx, INamespaceSymbol ns) => NamespaceFactory.Instance.CreateEntity(cx, ns);
public static Namespace Create(Context cx, INamespaceSymbol ns) => NamespaceFactory.Instance.CreateEntity2(cx, ns);

class NamespaceFactory : ICachedEntityFactory<INamespaceSymbol, Namespace>
{
Expand All @@ -41,5 +41,14 @@ class NamespaceFactory : ICachedEntityFactory<INamespaceSymbol, Namespace>
}

public override TrapStackBehaviour TrapStackBehaviour => TrapStackBehaviour.NoLabel;

public override int GetHashCode() => QualifiedName.GetHashCode();

string QualifiedName => symbol.ToDisplayString();

public override bool Equals(object obj)
{
return obj is Namespace ns && QualifiedName == ns.QualifiedName;
}
}
}
18 changes: 9 additions & 9 deletions csharp/extractor/Semmle.Extraction.CSharp/Entities/Property.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -24,9 +24,6 @@ public override IId Id
}
}

protected Accessor Getter { get; set; }
protected Accessor Setter { get; set; }

public override void Populate()
{
ExtractAttributes();
Expand All @@ -37,12 +34,13 @@ public override void Populate()
Context.Emit(Tuples.properties(this, symbol.GetName(), ContainingType, type.TypeRef, Create(Context, symbol.OriginalDefinition)));

var getter = symbol.GetMethod;
if (getter != null)
Getter = Accessor.Create(Context, getter);

var setter = symbol.SetMethod;
if (setter != null)
Setter = Accessor.Create(Context, setter);

if (!(getter is null))
Method.Create(Context, getter);

if (!(setter is null))
Method.Create(Context, setter);

var declSyntaxReferences = IsSourceDeclaration ?
symbol.DeclaringSyntaxReferences.
Expand Down Expand Up @@ -100,7 +98,9 @@ public override Microsoft.CodeAnalysis.Location FullLocation

public static Property Create(Context cx, IPropertySymbol prop)
{
return prop.IsIndexer ? Indexer.Create(cx, prop) : PropertyFactory.Instance.CreateEntity(cx, prop);
bool isIndexer = prop.IsIndexer || prop.ExplicitInterfaceImplementations.Any(e => e.IsIndexer);

return isIndexer ? Indexer.Create(cx, prop) : PropertyFactory.Instance.CreateEntity(cx, prop);
}

public void VisitDeclaration(Context cx, PropertyDeclarationSyntax p)
Expand Down
2 changes: 1 addition & 1 deletion csharp/extractor/Semmle.Extraction.CSharp/Entities/Types/NamedType.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -174,7 +174,7 @@ public NamedTypeRef(Context cx, INamedTypeSymbol symbol) : base(cx, symbol)
referencedType = Type.Create(cx, symbol);
}

public static NamedTypeRef Create(Context cx, INamedTypeSymbol type) => NamedTypeRefFactory.Instance.CreateEntity(cx, type);
public static NamedTypeRef Create(Context cx, INamedTypeSymbol type) => NamedTypeRefFactory.Instance.CreateEntity2(cx, type);

class NamedTypeRefFactory : ICachedEntityFactory<INamedTypeSymbol, NamedTypeRef>
{
Expand Down
2 changes: 1 addition & 1 deletion csharp/extractor/Semmle.Extraction.CSharp/Entities/Types/Type.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -157,7 +157,7 @@ protected void ExtractType()
var param = invokeMethod.Parameters[i];
var originalParam = invokeMethod.OriginalDefinition.Parameters[i];
var originalParamEntity = Equals(param, originalParam) ? null :
DelegateTypeParameter.Create(Context, originalParam, Create(Context, ((INamedTypeSymbol)symbol).ConstructedFrom));
DelegateTypeParameter.Create(Context, originalParam, Create(Context, ((INamedTypeSymbol)symbol).OriginalDefinition));
DelegateTypeParameter.Create(Context, param, this, originalParamEntity);
}

Expand Down
121 changes: 83 additions & 38 deletions csharp/extractor/Semmle.Extraction/Context.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -43,28 +43,90 @@ public SemanticModel Model(SyntaxNode node)
int NewId() => TrapWriter.IdCounter++;

/// <summary>
/// Gets the cached label for the given entity, or creates a new
/// (cached) label if it hasn't already been created. The label
/// is set on the supplied <paramref name="entity"/> object.
/// Creates a new entity using the factory.
/// </summary>
/// <returns><code>true</code> iff the label already existed.</returns>
public bool GetOrAddCachedLabel(ICachedEntity entity)
/// <param name="factory">The entity factory.</param>
/// <param name="init">The initializer for the entity.</param>
/// <returns>The new/existing entity.</returns>
public Entity CreateEntity<Type, Entity>(ICachedEntityFactory<Type, Entity> factory, Type init) where Entity : ICachedEntity
{
var id = GetId(entity);
if (id == null)
throw new InternalError("Attempt to create a null entity for {0}", entity.GetType());
return init == null ? CreateEntity2(factory, init) : CreateNonNullEntity(factory, init);
}

Label existingLabel;
if (labelCache.TryGetValue(id, out existingLabel))
/// <summary>
/// Creates a new entity using the factory.
/// Uses a different cache to <see cref="CreateEntity{Type, Entity}(ICachedEntityFactory{Type, Entity}, Type)"/>,
/// and can store null values.
/// </summary>
/// <param name="factory">The entity factory.</param>
/// <param name="init">The initializer for the entity.</param>
/// <returns>The new/existing entity.</returns>
public Entity CreateEntity2<Type, Entity>(ICachedEntityFactory<Type, Entity> factory, Type init) where Entity : ICachedEntity
{
using (StackGuard)
{
entity.Label = existingLabel;
return true;
var entity = factory.Create(this, init);

if (entityLabelCache.TryGetValue(entity, out var label))
{
entity.Label = label;
}
else
Copy link
Copy Markdown
Contributor

@hvitved hvitved Dec 19, 2018

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

redundant

Copy link
Copy Markdown
Contributor Author

@calumgrant calumgrant Dec 20, 2018

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I prefer branches myself -- I moved the return out of the branches instead.

{
var id = entity.Id;
#if DEBUG_LABELS
CheckEntityHasUniqueLabel(id, entity);
#endif
label = new Label(NewId());
entity.Label = label;
entityLabelCache[entity] = label;
DefineLabel(label, id);
if (entity.NeedsPopulation)
Populate(init as ISymbol, entity);
}
return entity;
}
}

entity.Label = new Label(NewId());
DefineLabel(entity.Label, id);
labelCache[id] = entity.Label;
return false;
#if DEBUG_LABELS
private void CheckEntityHasUniqueLabel(IId id, ICachedEntity entity)
{
if (idLabelCache.TryGetValue(id, out var originalEntity))
{
Extractor.Message(new Message { message = "Label collision for " + id.ToString(), severity = Severity.Warning });
}
else
{
idLabelCache[id] = entity;
}
}
#endif

private Entity CreateNonNullEntity<Type, Entity>(ICachedEntityFactory<Type, Entity> factory, Type init) where Entity : ICachedEntity
{
if (objectEntityCache.TryGetValue(init, out var cached))
return (Entity)cached;
Copy link
Copy Markdown
Contributor

@hvitved hvitved Dec 19, 2018

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Is this cast needed?

Copy link
Copy Markdown
Contributor Author

@calumgrant calumgrant Dec 20, 2018

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yes - it's cached as an ICachedEntity and could theoretically give an InvalidCastException if you try to create it with a different type next time.

Copy link
Copy Markdown
Contributor

@hvitved hvitved Dec 20, 2018

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ah, I failed to see that Entity was a type parameter; misread it as IEntity...


using (StackGuard)
{
var label = new Label(NewId());
var entity = factory.Create(this, init);
entity.Label = label;

objectEntityCache[init] = entity;

var id = entity.Id;
DefineLabel(label, id);

#if DEBUG_LABELS
CheckEntityHasUniqueLabel(id, entity);
#endif

if (entity.NeedsPopulation)
Populate(init as ISymbol, entity);

return entity;
}
}

/// <summary>
Expand All @@ -90,25 +152,6 @@ public bool ExtractGenerics(ICachedEntity entity)
}
}

/// <summary>
/// Gets the ID belonging to cached entity <paramref name="entity"/>.
///
/// The ID itself is also cached, but unlike the label cache (which is used
/// to prevent reextraction/infinite loops), this is a pure performance
/// optimization. Moreover, the label cache is injective, which the ID cache
/// need not be.
/// </summary>
IId GetId(ICachedEntity entity)
{
IId id;
if (!idCache.TryGetValue(entity, out id))
{
id = entity.Id;
idCache[entity] = id;
}
return id;
}

/// <summary>
/// Creates a fresh label with ID "*", and set it on the
/// supplied <paramref name="entity"/> object.
Expand All @@ -120,7 +163,11 @@ public void AddFreshLabel(IEntity entity)
entity.Label = label;
}

readonly Dictionary<IId, Label> labelCache = new Dictionary<IId, Label>();
#if DEBUG_LABELS
readonly Dictionary<IId, ICachedEntity> idLabelCache = new Dictionary<IId, ICachedEntity>();
Copy link
Copy Markdown
Contributor

@hvitved hvitved Dec 19, 2018

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Add #if DEBUG_LABELS

#endif
readonly Dictionary<object, ICachedEntity> objectEntityCache = new Dictionary<object, ICachedEntity>();
readonly Dictionary<ICachedEntity, Label> entityLabelCache = new Dictionary<ICachedEntity, Label>();
readonly HashSet<Label> extractedGenerics = new HashSet<Label>();

public void DefineLabel(IEntity entity)
Expand All @@ -134,8 +181,6 @@ void DefineLabel(Label label, IId id)
TrapWriter.Emit(new DefineLabelEmitter(label, id));
}

readonly Dictionary<object, IId> idCache = new Dictionary<object, IId>();

/// <summary>
/// Queue of items to populate later.
/// The only reason for this is so that the call stack does not
Expand Down
4 changes: 2 additions & 2 deletions csharp/extractor/Semmle.Extraction/Entities/Assembly.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -69,8 +69,8 @@ public override IId Id
get
{
return assemblyPath == null
? new Key(assembly, ";assembly")
: new Key(assembly, "#file:///", assemblyPath.Replace("\\", "/"), ";assembly");
? new Key(assembly, ";sourcefile")
: new Key(assembly, "#file:///", assemblyPath.Replace("\\", "/"), ";sourcefile");
}
}
}
Expand Down
Loading