# Questions tagged [performance]

The tag has no usage guidance.

118 questions
Filter by
Sorted by
Tagged with
134 views

### Probability in Dynamic frame aloha

If I've RFID Collision Arbitration System that is based on multi-frame dynamic frame ALOHA. How can compute the probability of the average tag resolution $L_n$? ,$P_s$ is probability for packet ...
9k views

### How do I calculate the speedup properly?

I am trying to calculate the speedup of this, but I am getting the wrong answer: Assuming that we have a program where we have two execution phases. One phase takes 1 time unit to execute and can ...
44 views

Apologies if this is the wrong place to ask. For my experiment, I have a single-page application and a multi-page application. I am testing them with an exponential distributed delay throttling. The ...
239 views

### Sorting networks hybrid sort

I saw an answer about the fastest way to sort an array with 6 elements. Turns out that using a sorting network is the best choice. If sorting networks are the fastest way to sort a small(< 16 ...
66 views

### Are fractions more computationally “expensive” than whole numbers?

I have a problem where the values are represented to humans as [0, .5, 1, ..., 8] But the function is massively recursive (game trees for a set of increasingly intractable problems) so I'm wondering ...
192 views

### What is the basic idea behind the usage of TLBs?

I know how Translation Lookaside Buffers work, and i also know we use them to improve the performance of data/program access by storing the recent page numbers - frame numbers in a memory cache. The ...
394 views

### GCD of a pair of products

I have two numbers, which are each the product of a large number of smaller numbers that I know. I want to find the GCD (Greatest common divisor) of these two numbers. Is there any way I can make use ...
399 views

### Changing Rabin-Karp without modulo to Rabin-Karp with modulo

I am trying to solve a string matching problem using Rabin-karp algorithm. I made use of Horner's method for calculating hash function, but I forgot to use modulo operator. It's like this now. (this ...
39 views

### Estimating the run time of a program according to a given CPU performance

When we have a recurrence relation of a program, as an example: T(N) = N log N + 9N + 55 and the CPU capability let's say (10^6) or any other number. What is ...
191 views

### How to get the quick answer to the “Is there AT LEAST ONE subset that contains all given elements?” question if the set of subsets is very large?

I have a very large amount of objects that look like this: ...
822 views

### What is the Effect of Hidden Layer Size?

I aim to gain more intuition with regards to the role of a hidden layer in a neural network architecture. And further to understand whether my classification problem is a linear one or not. Here is ...
309 views

### Tips for improving implementation of Wagner-Fischer-algorithm

So I'm working on an implementation of a Wagner-Fischer-Algorithm for an online programming challenge site, but I can't seem to push the time down to where it needs to be. The assignment is to, for a ...
133 views

### Why computer take long time to open huge text files? [closed]

Im not sure if this the right place to ask but I'm wondering why a computer takes forever to open huge text file like 1GB but if I open a video file (mkv) for example with 10GB like a movie it will be ...
533 views

### Best way to merge different trees to single data structure?

I trained an XGBoost model that classifies 50 different classes, therefore it generates a lot of boosters (trees). Also, I wrote a script that turns trained model to C++ code and it works really fast ...
1k views

### Understanding Amdahl's Law calculation

I have a homework problem: Calculate the overall speedup of a system that spends 40% of its time in calculations with a processor upgrade that provides for 100% greater throughput. Which is a pretty ...
51 views

### The impact of caching on the system performance or on the user experience

I am working on modeling a certain system's cache layer and comparing two algorithms. One outperforms the other one; it shows the higher cache hit rate (%). But what is important is the impact of ...
50 views

### How to measure the degree of randomness in Disk I/Os?

Most disk-based system's performance heavily depends on its disk access patterns. So maximizing the sequential I/Os while avoiding the random I/Os is a typical goal in performance perspective. I am ...
2k views

### Why do we have to trade abstraction for speed?

Why can high-level languages seemingly never reach lower-level languages in terms of speed? Examples of high-level languages would be Python, Haskell, and Java. Low-level languages would be trickier ...
288 views

### Hashtable vs cache-oblivious

This question has been asked in the theoretical community, but deemed as too practical. I am moving it here, I hope it is on-topic. I'd like to know more about real performances of data structures, ...
81 views

### Performance on modifying cycle time

I learnt in my computer architecture course on Caches, that if we keep the memory speed of a machine the same and half the clock cycle time, the miss penalty doubles. Why does this happen? What is ...
110 views

### Is the memory usage of total languages deterministic?

I'm interested in the memory usage of various programming languages when implemented on actual hardware. I believe that a Turing-complete programming language has, in general, unknowable memory usage ...
2k views

### Why is a (collision-less) hashtable lookup really O(1)?

Disclaimer: I know there are similar sounding questions already here and on Stackoverflow. But they are all about collisions, which is not what I am asking for. My question is: why is collision-less ...
133 views

### Scientifically acceptable method for comparing performance of algorithms

I am comparing several different algorithms for navigation applications. Since I may possibly be publishing a paper comparing the performance of these algorithms with each other, I was wondering the ...
364 views

### Can a vectorized computation always be parallelized?

If the question appears vague, I'll gladly clarify. It's not tied to a programing language. If there is a language dependency in the answer, one can place it in the context of Python, R, VB, ...
112 views

### Is program analysis part of programming language theory?

If I am correct, programming language theory studies syntax and semantics of programming languages, and design and implementation of programming languages (e.g. compiler, ...) Does programming in ...
43 views

### Better Algorithm to determine the number of all TRUE rows in a logical matrix

I have a matrix of logicals (TRUE, FALSE) and I need to count the number of rows that contain only ...
705 views

### Do recursive algorithms generally perform better than their for-loop counterpart?

I'm sure this is not a challenge for you but it remains an open question for me: Is it wise to prefer a recursive algorithm over its for-loop counterpart? E.g. take the evaluation of the natural ...
442 views

### In an Inverted Page Table, will following chains happen very often for small addresses?

I just learned about the Inverted Page Table and immediately thought about the chaining model used. If two processes use the same virtual address, resolving the address will have to include following ...
1k views

### How to compare the time-complexity of an optimized algorithm with that of the original?

I had an algorithm with time-complexity of $O(h\times w)$, knowing $h$ is the height and $w$ is the width of an image being processed (or a simple matrix of size $h\times w$). I managed to reduce the ...
43 views

### Counting words: performance of loop vs. list comprehensions [duplicate]

I am no computer scientist, so I can be naively missing some commonly implemented optimization strategies but... Looking at two ways of counting words in a text (shown below), I tend to think that ...
378 views

### Do functional algorithms require more memory than imperative algorithms? [closed]

Let's suppose we are counting words in string. We split it so what we have is an array of strings. I'll use Python as an example. The imperative approach would as follows: ...
470 views

### What features should a critical section have to maximize performance?

Critical sections limit performance by constraining parallel execution and adding overhead. What features should a critical section have for improving performance?
93 views

### What is the size of a queue associated with a resource when the resource becomes a bottleneck?

In Software Performance and Scalability: A Quantitative Approach - Henry H. Liu, the author is presenting a scenario where the hardware becomes a bottleneck. In one ot the tests, he is checking the ...
61 views

### Correlation between high cpu/ram usage and poor computer performance [closed]

I'm researching electromigration and the effects of high cpu/ram usage on a computer. There are tons of discussions on these topics taking place via forums and message boards, but I am looking for ...
4k views

5k views

### Amdahl's law or gustafson's law

I am a little confused which of the two laws above i should use: Suppose I have a computer program that can be parallelized by 70%. 30% cannot be parallelized. Every single data (100% of data) will ...
8k views

### MIPS rating formula

Could you please help me to understand the mathematics behind MIPS (million instructions per second) rating formula? The formula for MIPS is:  \text{MIPS} = \frac{ \text{Instruction count}}{\...
249 views

### CPU Performance

Please, help me to understand the mathematics behind the following formula of CPI. Why do we calculate CPI the way it's done on the pic?
129 views

### How can I evaluate an algorithm for a NP-Hard problem?

I have written a program to calculate the number of stable partition in a graph. ( That is: find which partition of the nodes does not have edges between nodes of the same block. ) The professor, ...
804 views

### Why analysis of Aloha protocol uses Poisson distribution?

Pretty much in all of the analysis of the Aloha protocol that I read, it is assumed that the distribution of packet arrivals is Poisson. What is the rationale behind it? Isn't it actually binomial ...
671 views

### Bare Metal Operating Systems in High Performance Computing

Few years back, I stumbled across Return Infinity - the OS framework designed around flat, 64bit memory model, with minimal MMU / VM overhead, etc. I'm wondering if there are any public benchmarks or ...
752 views

### Why is the OS design able to reduce power consumption?

I have read that OSes like Android and iOS are somehow optimised to improve battery life. My understanding is that a CPU executes a certain number of operations in a certain time, so I would think ...
400 views

11k views

### Performance of microkernel vs monolithic kernel

A microkernel implements all drivers as user-space programs, and implements core features like IPC in the kernel itself. A monolithic kernel, however, implements the drivers as a part of the kernel (e....
16k views

### Why is the throughput (performance) of the Slotted Aloha protocol ≈ 0.36

I've read that the throughput - that is, the amount of good useful messages relative to capacity - of the Slotted ALOHA protocol for communication networks is roughly 0.36%. But its not clear how we ...
813 views

### Why is the throughput (performance) of the Aloha protocol ≈ 0.18?

I've read in a few places (like here that the throughput - that is, the amount of good useful messages relative to capacity - of the ALOHA protocol for networks is roughly 0.18%. But its not clear ...
2k views

### Definition of “c-competitive” algorithm

What is the definition of a "c-competitive" algorithm? For example what does it mean, if we say that there is a 2-competitive algorithm for packet routing?
5k views

### How do people measure performance overhead?

How do people measure performance overhead? Whenever someone is bragging about how their program or application performs better than another, they talk about particular measurements, eg time, ...
Let's have an array where first half are of value 50 and the second half 100. What would be the asymptotic performance when sorting using Quicksort. I think it it should be $O(n^2)$ as for array of ...