DEV Community: Suprise Nkosi

Topics in database development and program parallelism

Suprise Nkosi — Sat, 05 Feb 2022 13:06:06 +0000

Introduction

Concurrency and parallelism are incredibly important topics in computer science, and are also a hot topic in industry today. Computers are gaining more and more cores, yet many programmers aren’t prepared to fully utilize them [7]. we are going to cover some of the highly cited topics and subjects in the area of parallel programming and concurrency, the topics are not exhaustive, however the main goal or objective is to make them to be.

Granularity

The size of data items is often called the data item granularity, to be precise the amount of computation in relation to communication [4] , coarse granularity refers to large item sizes, data is communicated infrequently, after larger amounts of computation, Fine granularity refers to small item sizes, individual tasks are relatively small in terms of code size and execution time. The data is transferred among processors frequently in amounts of one or a few memory words. The coarse granularity of data accesses is one of the reasons why B+tree indexing is not efficient for use in parallel computations, it is known that the larger the data item size is, the lower the degree of concurrency permitted, paraphrasing “the finer the granularity, the greater the potential for parallelism and hence speed-up, but the greater the overheads of synchronization and communication” [4].

Both Fine and Coarse Granularity have their own drawbacks, In order to attain the best parallel performance, the best balance between load and communication overhead needs to be found. If the granularity is too fine, the performance can suffer from the increased communication overhead. On the other side, if the granularity is too coarse, the performance can suffer from load imbalance. [4]

Simple Example, a business address can be recorded, with coarse granularity,

business address = 200 2nd Ave. South #358, St. Petersburg, FL 33701-4313 USA,

as a single field a string or as a finer granularity, this is a method most followed by Doctrine ORM when modelling data entities.

street address = 200 2nd Ave. South #358
city = St. Petersburg
state = FL
postal code = 33701-4313
country = USA

This principles are used in the design and development of API’s, one use case maybe in the event in which remote calls are likely to be slower than local calls, the parameters in remote methods should be relatively coarse-grained. A coarse-grained object contains more data than a fine-grained one, so fewer access calls are required. For the same reason, the parameters of the methods called by web service clients should also be coarse-grained.[5]

Locks Vs Latches as a concurrency control technique

There is an important distinction between locks and latches when discussing how the DBMS protects its internal elements, A lock is a higher-level, logical primitive that protects the contents of a database (e.g., tuples, tables,databases) from other transactions. Transactions will hold a lock for its entire duration. Database systems can expose to the user the locks that are being held as queries are run. Latches are the low-level protection primitives used for critical sections the DBMS’s internal data structures (e.g., data structure, regions of memory) from other threads. Latches are held for only the duration of the operation being made.[6] Latches can be implemented by using OS mutex,

SMID (Single Instruction Multiple Data) – a class of parallel computers in Flynn’s Classification. It outlines the computers with multiple processing elements that can perform the same operation on multiple data points simultaneously.It has been extensively used in database research to boost the performance of database operations. The paper in references index [3] shows how the performance of mergesort, a classical sort algorithm, can be improved, when equipped with SIMD, it has been shown that the SIMD-based implementation of many database operators, including scan, aggregation, indexing and join, perform much better than its non-SIMD counterpart.

Competitiveness of In-memory databases

DRAM (Dynamic random-access memory) has orders of magnitude higher bandwidth and lower latency than hard disks, or even flash memory for that matter,With exponentially increasing memory sizes and
falling prices, it is now frequently possible to accommodate
the entire database and its associated indices in memory,thereby completely eliminating the significant overheads of slow disk accesses.

NUMA Non-uniform memory access (NUMA) is a computer memory design used in multiprocessing, where the memory access time depends on the memory location relative to the processor. Under NUMA, a processor can access its own local memory faster than non-local memory (memory local to another processor or memory shared between processors). The benefits of NUMA are limited to particular workloads, notably on servers where the data is often associated strongly with certain tasks or users [8]. NUMA architecture opens up opportunities for optimization in terms of cache coherence and memory access, which
can significantly hinder the performance if not taken into design . Since accessing the memory affiliated with remote (non-local) NUMA nodes is substantially costlier than accessing local memory, the major direction for NUMA-aware optimization is to reduce the accesses of remote memory, and meanwhile keep load balancing among NUMA nodes.
Many systems have been proposed with NUMA aware optimizations. ERIS is an in-memory storage engine which employs an adaptive partitioning mechanism to realize NUMA topology and hence reduce remote memory accesses.

Conclusion

Concurrency and parallelism can speed up a lot of classical algorithms and help produce faster programs as a result we dedicate our effort in covering a lot of topics under this category follow me on twitter for more updates.

References

https://www.brainkart.com/article/Granularity-of-Data-Items-and-Multiple-Granularity-Locking_11567/
https://www.geeksforgeeks.org/difference-between-fine-grained-and-coarse-grained-simd-architecture/
J. Chhugani, A. D. Nguyen, V. W. Lee, W. Macy, M. Hagog, Y.-K. Chen, A. Baransi, S. Kumar, and P. Dubey. Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture. PVLDB,1(2):1313–1324, 2008.
https://en.wikipedia.org/wiki/Granularity
https://docs.oracle.com/cd/E19798-01/821-1841/gipkv/index.html
https://15445.courses.cs.cmu.edu/fall2020/notes/09-indexconcurrency.pdf
http://web.mit.edu/rust-lang_v1.25/arch/amd64_ubuntu1404/share/doc/rust/html/book/first-edition/concurrency.html
https://en.wikipedia.org/wiki/Non-uniform_memory_access

My Nativescript Experience

Suprise Nkosi — Sat, 11 Apr 2020 07:42:19 +0000

Well the quest start from a need to develop a next generation mobile application to solve a particular well posed problem. Then comes the element of time to progression ratio. Well from this element one decides “I need a technology that will allow me to save time in developing this mobile application whilst not compromising code quality”, then you decide to surf the web or ask someone they tell you about native script.

You compare the time saving features that native script offers with other alternatives

Time saving Features

Cross platform development
Third party libraries and Plugins
The development Pipeline
Debbuging Tools
Availability of system development kits
Adaptability and Learning Rate

Well as for me looking at all those factors native script prevailed comparing to competing technologies.

Then the problem starts, we are at a point in which i have confidence on the technology above other techs. Then i have to get my hands dirty on coding.

Problem 1: Setting Up the Environment

The technology offers full-setup which installs all required tools for local development and also offers the CLI - installation only, Full setup has a great initial setup costs in terms of time and internet connection related costs, from this cost one might decide to go for the CLI installation and get to work with native script, with a good hypothesis one might conclude that more than 70% choose this setup. However this setup comes with a limitation you can only preview your app using the nativescript preview app and that app by its self has a limitation, most of unverified plugins do not work on it.

How can this be a problem? Well lets say you have CLI setup and you continue to develop and write about 1000 lines of code and you decide a plugin might be help-full, then you install the plugin, you run command tns preview you get the warning message that plugin is not included on preview. Then you dont have a choice but to install the Full setup. Now the cost of setup includes both the full setup and the time component of CLI setup. With only the above knowledge assuming you dont have any knowledge about how sidekick works this event can be very discouraging, due to the complexity of the full setup.

Problem 2: Full Setup

Now you are done with the full setup assuming everything was done correctly, you want to preview your app on a connected device, you execute command “tns run android” the build method used by nativescript is incremental which is a complement to the technology. Lets assume its your first time running the command it can take about 7minutes to complete on a average machine. You understand ok that was my first build, then you run the incremental build you find out it takes about 80% of the initial build time to complete, then that when the real problem starts. Which is lower productivity due to the process that the technology applies.

The Core Problem

Native script is a good technology to work with if you have experience with its downfalls, my real challenge using this technology is productivity, productivity decreases asymptotically as you continue working with it. However if you expect the downfalls you can prepare for them, and i dont wanna lie you will love the technology.

Linear Congruential generator

Suprise Nkosi — Sun, 12 Jan 2020 15:40:24 +0000

This is a basic explanation of linear congruental generator, a method of generating random numerical values, the generating formulae is described by the equation

Xn+1 = (A x Xn+B) Mod M

A,B and M are constants
The value X used to initialize the sequence is called the seed. The sequence of numbers generated are random however they have a period in which the whole function repeat its values, making it a random but a predictable generator.

The implementation of this algorithm in javascript would be as follows


var m =11,
    a =7,
    c =5;
var z = 0;

var rand = function(){

z=(a*z+c)%m;

return z;
};

for(i=0;i<20;i++){
  console.log(rand());
}

Implementation of insertion sort algorithm in Javascript

Suprise Nkosi — Thu, 09 Jan 2020 08:35:45 +0000

Insertion-sort is one of the most common sorting algorithms used by computer programmers to sort their data. It takes an input which is a sequence of n finite set of numbers , then a permutation (reordering) is applied to the sequence, such that the element with index[n] in the sequence is less or equal to the element with index[n+1] or vise versa .

The numbers we wish to sort are called keys(elements), due to the fact that the inputs are a sequence, the n numbers are going to come to us in a form of an array. before i propose to you a pseudo code and its implementation, i will introduce an analogy of sorting a hand of cards to better illustrate how the algorithm works.

lets say you have 5cards all are face-down, you pick the first card and you turn it face up, then you have to pick another card and turn it face up (insertion) so that you have a degree of comparison (2-cards), you iterate the process till all cards are face up and sorted.

Lets consider the following pseudo code from chapter 2 of the book titled introduction to algorithms by Cormen et al

for j = 2 to A.length
   key= A[j]
   i= j-1
   while i>0 and A[i]> key
    A[i+1]=A[i]
    i=i-1
A=[i+1] = key

The design approach used for its implementation in javascript is an incremental approach, and it looks something like this.

var A = [3,1,9,5,4];
for (let index = 0; index < A.length; index++) {
const key = A[index]
let i = index -1;
while (i >= 0 & A[i]> key) {
A[i+1] = A[i]
i = i-1;
A[i+1] = key
}
// console.log(key);
}
console.log(A);
//Sort Ascending

To sort in descending order you only need to change the A[i]>key comparison sign to <. It is of paramount to note that the following code does the same as the above code.

var A = [3,1,9,5,4];
A.sort(function(a,b){
return a-b;
})
console.log(A)

If you would like me to share more information with you, you can direct message me on twitter .