Preface

Today, let's share the performance problems and solutions we encounter in our daily work , It's fragmented , It will be updated continuously in the future ( The operating environment is .net core 3.1)

The cases shared this time are all from actual production , Simplified as an example

Part 1( As a simple data carrier class and struct Performance comparison of )

About class and struct The difference between , Based on experience , In most scenarios of actual development , Will use class As a data type , But if it's as A huge collection of simple data The type of , And it doesn't involve copying 、 When transferring parameters and other operations , Consider using struct, Because relative to the reference type class Distributed on the heap , As a value type struct It's distributed on the stack , In this way, it has faster creation speed and saves pointer space , List 3000 The set of ten thousand elements is represented by class and struct As a type , Do the following test ( The test tool is vs Self contained Diagnostic Tools):

class Program {
static void Main (string[] args) {
var structs = new List<StructTest> ();
var stopwatch1 = new Stopwatch ();
stopwatch1.Start ();
for (int i = 0; i < 30000000; i++) {
structs.Add (new StructTest { Id = i, Value = i });
}
stopwatch1.Stop ();
var structsTotalMemory = GC.GetTotalMemory (true);
Console.WriteLine ($" Using structs consumes memory :{structsTotalMemory} byte , Time consuming :{stopwatch1.ElapsedMilliseconds} millisecond ");
Console.ReadLine ();
} public struct StructTest {
public int Id { get; set; }
public int Value { get; set; }
}
}

class Program {
static void Main (string[] args) {
var classes = new List<ClassTest> ();
var stopwatch2 = new Stopwatch ();
stopwatch2.Start ();
for (int i = 0; i < 30000000; i++) {
classes.Add (new ClassTest { Id = i, Value = i });
}
stopwatch2.Stop ();
var classesTotalMemory = GC.GetTotalMemory (true);
Console.WriteLine ($" Using classes consumes memory :{classesTotalMemory} byte , Time consuming :{ stopwatch2.ElapsedMilliseconds} millisecond ");
Console.ReadLine ();
} public struct StructTest {
public int Id { get; set; }
public int Value { get; set; }
}
}

By calculation ,struct The consumption of space includes : Each structure contains two integers stored on the stack , Each integer accounts for 4 Bytes , Each structure accounts for 8 byte , multiply 3000 Ten thousand elements occupy 240,000,000 byte , It is consistent with the actual measurement ;

and class The consumption of space is more complicated , Contains : Each class contains two integers that exist on the heap , Each integer accounts for 4 byte , Two pointers on the stack , the reason being that 64 Bit computer, so each pointer takes 8 byte , Plus a pointer to the class itself 8 byte , Per class 24 byte (4+4+8+8+8), multiply 3000 Ten thousand elements occupy 960,000,000 byte , It is consistent with the actual measurement . In terms of time consumption class Because of the memory allocation , Time consuming 5 About seconds , Far greater than struct Of 1.5 second .

Based on this test ,

More about class and struct Please go to the official Microsoft document    https://docs.microsoft.com/en-us/dotnet/standard/design-guidelines/choosing-between-class-and-struct

Part 2( Optimization of nested traversal of sets )

About nested set traversal , We iterate through it in two levels of nested sets , Each collection holds 10000 An unordered integer , Then count the number of elements that have two sets at the same time , From top to bottom in regular nested loops , Use HashSet type , Reference resources PostgreSQL Of MergeJoin For example :

class Program {
static void Main (string[] args) {
var l1s = new List<int> ();
var l2s = new List<int> ();
var rd = new Random ();
for (int i = 0; i < 10000; i++) {
l1s.Add (rd.Next (1, 10000));
l2s.Add (rd.Next (1, 10000));
} var sw = new Stopwatch ();
sw.Start ();
var r = new HashSet<int> ();
foreach (var l1 in l1s) {
foreach (var l2 in l2s) {
if (l1 == l2) {
r.Add (l1);
}
}
}
sw.Stop ();
Console.WriteLine ($" Total found {r.Count} Two elements exist at the same time l1s and l2s, It took time {sw.ElapsedMilliseconds} millisecond ");
Console.ReadLine ();
}

class Program {
static void Main (string[] args) {
var l1s = new HashSet<int> ();
var l2s = new HashSet<int> ();
var rd = new Random ();
while (l1s.Count < 10000)
l1s.Add (rd.Next (1, 100000));
while (l2s.Count < 10000)
l2s.Add (rd.Next (1, 100000)); var sw = new Stopwatch ();
sw.Start ();
var r = new List<int> ();
foreach (var l1 in l1s) {
if (l2s.Contains (l1)) {
r.Add (l1);
}
}
sw.Stop ();
Console.WriteLine ($" Total found {r.Count} Two elements exist at the same time l1s and l2s, It took time {sw.ElapsedMilliseconds} millisecond ");
Console.ReadLine ();
}

class Program {
static void Main (string[] args) {
var l1s = new List<int> ();
var l2s = new List<int> ();
var rd = new Random ();
for (int i = 0; i < 10000; i++) {
l1s.Add (rd.Next (1, 10000));
l2s.Add (rd.Next (1, 10000));
} var sw = new Stopwatch ();
sw.Start ();
var r = new List<int> ();
l1s = l1s.OrderBy (x => x).ToList ();
l2s = l2s.OrderBy (x => x).ToList ();
var l1index = 0;
var l2index = 0;
for (int i = 0; i < 10000; i++) {
var l1v = l1s[l1index];
var l2v = l2s[l2index];
if (l1v == l2v) {
r.Add (l1v);
l1index++;
l2index++;
}
if (l1v > l2v && l2index < 10000)
l2index++;
if (l1v < l2v && l1index < 10000)
l1index++; if (l1index == 9999 && l2index == 9999)
break;
}
sw.Stop ();
Console.WriteLine ($" Total found {r.Count} Two elements exist at the same time l1 and l2s, It took time {sw.ElapsedMilliseconds} millisecond ");
Console.ReadLine ();
}

The result shows that , Regular nested traversal takes time 1 second , The time complexity is O(n2); Use HashSet Time consuming 3 millisecond ,HashSet The bottom layer uses hash table , By looping the outer set , The inner set is directly hash lookup , The time complexity is O(n); Reference resources PostgreSQL Of MergeJoin Thinking takes time 19 millisecond , The idea is to sort the set first , Then mark the current displacement , Using the property that array can subscript directly , The time complexity is O(n). thus it can be seen , For large data sets , We should pay special attention to nested loops .

More about merge join Please move the design idea of PostgreSQL Official documents of   https://www.postgresql.org/docs/12/planner-optimizer.html

It should be noted that , Whether it's hashing or sorting , Will introduce additional losses , After all, in the world of computers , Either to Time for space , Either to Space for time , If you want to optimize time or space at the same time, can you do it ? It's also possible in some scenarios , You can refer to my previous blog , adopt Memory mapped files Combined with what we're talking about today , You can try it .

If there are any questions , You are welcome to correct at any time , Sharing and trial and error is also a learning process , Thank you. ~

Everyday sharing : Share some optimization experience about time complexity and space complexity (C#) More articles about

  1. MongoDB Share the experience of optimization

    Here is a summary of the use of mongo What I learned , List a few things to pay attention to . 1. System parameters and mongo Parameter setting mongo The main parameters are storageEngine and directoryperdb, These two parameters don't start with ...

  2. from js Explain time complexity and space complexity

    1. Blog background Today, when a colleague is checking the code , Because the function writing performance is not very good , Was hit back and rebuilt , Consider very fear , Today I'd like to share an article with you js Explain the time complexity and space complexity of the blog 2. The representation of complexity I've seen it before , You may be ...

  3. C# Time complexity and space complexity of sorting algorithms commonly used in

    The time complexity and space complexity of the common sorting algorithm   The time complexity and space complexity of the common sorting algorithm Sequencing Worst time analysis Average time complexity stability Spatial complexity Bubble sort O(n2) O(n2) Stable O(1) Quick sort ...

  4. [Java Explore the outer part ]__ About time complexity and space complexity

    Preface We learned from the previous sorting algorithm , Classification of sorting algorithm , The criteria used in the comparison of efficiency , It includes time complexity and space complexity , At that time, because these two definitions are still relatively difficult to understand , So I decided to open a separate article , Record the learning process ...

  5. Algorithm time complexity 、 Spatial complexity ( Big O notation )

    What is algorithm ? The computer is an extension of the human brain , It exists mainly to help us solve problems . The algorithm in the computer field is to solve the problem and specify a series of simple instructions set . Different algorithms need different resources , for example : Execution time or memory consumption . If ...

  6. php Algorithm basis ---- Time complexity and space complexity

    Algorithm complexity is divided into time complexity and space complexity . Its role : Time complexity refers to the amount of computation required to execute the algorithm : And space complexity is the memory space needed to execute this algorithm . ( The complexity of the algorithm lies in the amount of resources needed by the computer when the algorithm is running , ...

  7. Python The time complexity and space complexity of language algorithms

    Algorithm complexity is divided into time complexity and space complexity . Its role : Time complexity refers to the amount of computation required to execute the algorithm : And space complexity is the memory space needed to execute this algorithm . ( The complexity of the algorithm lies in the amount of resources needed by the computer when the algorithm is running , ...

  8. Unity MMORPG Game optimization experience sharing

    https://mp.weixin.qq.com/s/thGF2WVUkIQYQDrz5DISxA Today by Unity Technical support engineer Gao Yan , According to the actual technical support work experience , Share how to Unity MMORP ...

  9. Baidu APP Mobile end network deep optimization practice sharing ( Two ): Network connection optimization

    This article by Baidu technology team “ Cai Rui ” Original published in “ Baidu App technology ” official account , The original topic is < Baidu App Network depth optimization series < Two > Connection optimization >, Thank the original author for his selfless sharing . One . Preface stay < Baidu APP Mobile terminal network ...

  10. Baidu APP Mobile end network deep optimization practice sharing ( One ):DNS Optimization

    This article by Baidu technology team “ Cai Rui ” Original published in “ Baidu App technology ” official account , The original topic is < Baidu App Network depth optimization series < One >DNS Optimize >, Thank the original author for his selfless sharing . One . Preface Network optimization is the client side of several major technologies ...

Random recommendation

  1. jq The foundation of selectors

    Jquery $ For selector Use jq You have to import jq file <script src="http://libs.baidu.com/jquery/2.0.0/jquery.min.js&qu ...

  2. eclipse + python dev

    error :Project interpreter not specified resolvent http://blog.csdn.net/magictong/article/details/7288732 install Py ...

  3. One through network transformation Ico To Png A little program for pictures (Ico2Png)

    Do software interface need to use ico file , Results skin library does not support ico Format icons , So I thought of ico convert to png. online ico turn png I don't seem to have much software , Instead, png turn ico It's a big one ~~~~~~~~~ To convert ic ...

  4. MVC Login authentication and authorization and read login error code

    Recently I realized a truth , Here to share : Education represents your past , Ability represents your present , Learning represents your future . Ten years east, ten years West , Don't deceive young people into being poor knowledge has no limit , Keep improving     I'm learning by myself recently MVC, There are many problems , Just a little summary ...

  5. vs2012+qt5.2.0 Environment building /vs2013 + qt5.3.2 Environment building

    classification : Windows Qt2014-01-17 00:50 15434 Human reading   Comment on (18)  Collection   report This article is invalid , Please refer to my new article : vs2013 + qt5.3.2 Environment building  ( http:/ ...

  6. JavaScript Floating point problems ( Multiplication )

    <script type="text/javascript"> var get_b_val_final=accMul(get_b_val,100)+"%&qu ...

  7. 2. How to install vmvare tools

    1. On the home page, click virtual machine reinstall vmvaretools, And then it will download tar.gz package 2.cd Go to the unpacking place , decompression sudo tar zxf ... 3. After decompression, it will generate a vmvare-toos-distri ...

  8. [Usaco2015 Jan]Grass Cownoisseur Tarjan Shrinkage point +SPFA

    I forgot to shrink when I took the exam , artificial dfs Analog pinch point , I didn't expect to run away 30 branch ,RB The outbreak of ... The side is repeatable , So in the same strongly connected component , No matter from which point in or out , All the points can be reached by one way .  To use a pinch point . Then I ...

  9. ES5 Inherit

    Prototype inheritance <script type="text/javascript"> function Father(){}// Constructors // Prototype attribute Father.prototy ...

  10. Uncaught SyntaxError: Invalid shorthand property initializer Report errors

    This mistake must be : hold ":" It has been written. "=" Number